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;
}
}
```