Gullele's Corner

I got this question while helping a friend on the course work. It is relatively simple question. But the way how it is approached can make a difference on efficiency.

The question is, given an array of numbers, you are to find if there are three numbers that would total the given number T.

If done in a very naive way, it can soar to o(n^3) like having three loops and checking the sum inside the third loop.. well.. this is a no no..

I have approached it in a log n ( for sorting) and n for (searching) approach..

package algorithm;

import java.util.Arrays;

/**
 * Given an array of integers, find if there are three numbers that would sum up to the 
 * number T
 * 
 * @author http://gullele.com
 *
 */
public class ThreeNumbersSummingT {
	public static void main(String[] args) {
		int[] test = new int[]{1,3,4,5,10,12, 18};
		ThreeNumbersSummingT summt = new ThreeNumbersSummingT();
		
		int[] response = summt.findThreeNumbers(test, 29);
		
		if (response.length > 1) {
			for(int num : response) {
				System.out.println(num);
			}
		} else {
			System.out.println(":( Couldn't find those three gems");
		}
				
	}
	
	public int[] findThreeNumbers(int[] nums, int t) {
		
		int[] indexes = new int[1];
		if (nums.length == 0 || nums.length <= 2) {
			return indexes;
		}
		
		//for primitive this would be quick sort so we have nlogn
		Arrays.sort(nums);
		
		int minIndex =0;
		int maxIndex = nums.length-1;
		int current = 1;
		while (minIndex != maxIndex) {
			if (nums[minIndex] + nums[maxIndex] + nums[current] == t) {
				int[] summingNumbers = new int[3];
				summingNumbers[0] = nums[minIndex];
				summingNumbers[1] = nums[current];
				summingNumbers[2] = nums[maxIndex];
				return summingNumbers;
			}
			
			int lookingFor = t-(nums[minIndex] + nums[maxIndex]);
			//if the number being sought is beyond the max, then jack up the min index
			if (lookingFor >= nums[maxIndex]) {
				minIndex++;
				current = minIndex + 1;
			} else if (nums[minIndex] + nums[maxIndex] + nums[current] < t) {
				current++;
			} else {
				maxIndex--;
				current = minIndex + 1;
			}
			
		}
		
		return indexes;
	}
}