finding three elements in an array whose sum is equal to a given number

Finding three elements in an array whose sum is equal to a given number(say trisum)

Here, for every element(arr[i]) that we pick, trisum-arr[i] gives us the bisum (algorithm to find a pair of elements that matches to sum k), hence we make use of our bisum algorithm to find a pair that matches to sum k

Assumption: The input array is sorted.

Example
arr: {1,2,3,4,5} and trisum is 8 then tri pairs are 1,3,4 and 1,2,5
Here lets say arr[i] is 1 then bisum=trisum-arr[i] i.e, bisum=8-1=7 therefore we should run bisum algorithm for sum 7

Time complexity for this algo: O(n^2) because for every element we need to find set of pairs

Note: If the array is not sorted the the complexity would be nlogn + O(n^2)

/**
 * find 3 elements in an array, that sum up to particular number with best
 * complexity
 * 
 * @author ntallapa
 * 
 */
public class TriPairSumCloseToK {

	public void getTriPair(int[] arr, int expectedTriSum) {
		for (int i = 0; i < arr.length; i++) {
			int expectedBiSum = expectedTriSum - arr[i];
			String output = getPair2(arr, expectedBiSum, i);
			if(!output.equalsIgnoreCase("")) {
				System.out.println(arr[i]+","+output.toString());
			}
		}
	}
	
	/**
	 * Find the pair in an array whose sum with complexity O(n). This assumes
	 * the array passed is sorted array and there are no duplicates in the 
	 * array
	 * @param arr
	 *            input array of elements
	 * @param expectedBiSum
	 *            sum for which pair of array elements needs to be searched
	 */
	public String getPair2(int[] arr, int expectedBiSum, int ignoreIndex) {
		int start = 0;
		int end = arr.length - 1;
		int sum = 0;

		// output array to record matching pairs
		StringBuilder arrs = new StringBuilder();

		while (start < end) {
			//
			if(start == ignoreIndex)
				start++;
			//
			if(end == ignoreIndex)
				end--;
			
			sum = arr[start] + arr[end];
			if (sum == expectedBiSum) {
				// we have found one pair, add it to our output array
				arrs.append(arr[start] + "," + arr[end] + ";");
				start++;
				end--;
			} else if (sum < expectedBiSum) {
				// if the sum of the pair is less than the sum we are searching
				// then increment the start pointer which would give us the sum
				// more than our current sum as the array is sorted
				start++;
			} else {
				// if the sum of the pair is greater than the sum we are 
				// searching then decrement the end pointer which would give us 
				// the sum less than our current sum as the array is sorted
				end--;
			}
		}
		return arrs.toString();
	}

	/**
	 * Client to test
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		TriPairSumCloseToK p = new TriPairSumCloseToK();

		// sorted array algo
		int[] arr1 = { 1, 2, 3, 4, 5 };
		p.getTriPair(arr1, 1);

	}
}