Finding a sum of unique triplet that is close to a given number in an array I asked one question on code review yesterday about my code style, logic and readability of code. Hence, today I kept all those suggestions in mind while solving a new problem question.

The question is such: Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example: given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

This is my solution:

 public int threeSumClosest(int[] num, int target) {
    if(num.length &lt; 3) {
        return 0;
    }
      Arrays.sort(num);
    int tempSum = Math.abs( target - ( num[0] + num[1] + num[2] ));
    int result = num[0] + num[1] + num[2];

    for (int index = 0; index &lt; num.length - 1; index++) {
        int j = index + 1;
        int k = num.length-1;
        while (j &lt; k){
            int newSum = Math.abs( target - ( num[index] + num[j] + num[k] ) );
            if( newSum == 0 ) {
                return ( num[index] + num[j] + num[k] ) ;
            }
            else if ( num[index] + num[j] + num[k] &lt; target ) {
                if( newSum &lt; tempSum ) {
                    tempSum = newSum;
                    result = num[index] + num[j] + num[k];
                }

                j++;
            }
            else {
                if( newSum &lt; tempSum ) {
                    tempSum = newSum;
                    result = num[index] + num[j] + num[k];
                }
                k--;
            }
        }//end of while loop
    }// end of for loop
    return result;
}


It would be great to hear back if I need to make further improvements. Any help will be highly appreciated. Also, Is there an approach which can solve this problem in less than \$O(n^2)\$.
Algorithm - Reducing search space

I'd define kMax as num.length - 1.

Then, do a binary search for the point at which num[0] + num[1] + num[k - 1] is too low, and num[0] + num[1] + num[k] is too high. Set kMax to k.

Next, do a binary search for the point at which num[i] + num[kMax - 1] + num[kMax] is too high, and num[i - 1] + num[kMax - 1] + num[kMax] is too low. Define iMin to be i - 1.

Start your for loop loop with index at iMin. At the start of each iteration, set k to kMax.

Instead of your current moving up/moving down scheme, just start downing k. As long as [i][j][k-1] is too high, kMax = k. When [i][j][k-1] is no longer too high, resume your uppy-downy scheme.

Whenever you increment i, check if [i][k-1][k] is too low. If so, increase i until [i][k-1][k] is no longer too low. Check if [i-1][k-1][k] gives a better match and store it as temp. 

AFter changing scope like this, check the opposite end of the scope. So if you just reduced k, check if [i][k-1][k] is too low. If you just increased i, check if [i][i+1][k] is too high. Do this until scope is stable.

Perhaps binary search could speed this (upping i and downing k) up too, but I'm not sure.

What this would do is potentially eliminate is a lot of your search space.

You see, if I gave you the number 42 to find in an array that contained random numbers between -500 and +200, -500, +199, +200 is simply too low. So you can kill off any number that's below -357, provided it's not the last number at or below -357.

This is a reduction of 20% of your search space with a simple binary search.

Additionally, once we get to -70, any number greater than 182 that is not the last number at or above 182 is not going to help.



Binary search is blazingly fast. 10000 elements can be searched through in 13-14 array accesses. 100000 elements - 17 array accesses.

Consider stopping binary search when your scope size is less than 128 (your code should go blazingly fast at that point anyway).

Your code

for (int index = 0; index &lt; num.length - 1; index++)

For an array of 3 elements... index &lt; num.length - 1 means index &lt; 3 - 1 means index &lt; 2.

So you've got a problem; You'll eventually check [1][2][2]. Your fix for this is while(j &lt; k), but I think you'll be better served by changing the for loop header to be for (int index = 0; index &lt; num.length - 2; index++) (changing index &lt; num.length - 1 to index &lt; num.length - 2). And then adding a comment WHY it is 2.

        int newSum = Math.abs( target - ( num[index] + num[j] + num[k] ) );
        if( newSum == 0 ) {
            return ( num[index] + num[j] + num[k] ) ;
        }
        else if ( num[index] + num[j] + num[k] &lt; target ) {
            //code
            result = num[index] + num[j] + num[k];


You have here, in a single iteration, 2 to 3 summations of num[index] + num[j] + num[k]. Some languages will cache these values. Some languages will not. I'd get in the habit of summing them once, then doing what you must.

        else if ( num[index] + num[j] + num[k] &lt; target ) {
            if( newSum &lt; tempSum ) {
                tempSum = newSum;
                result = num[index] + num[j] + num[k];
            }

            j++;
        }
        else {
            if( newSum &lt; tempSum ) {
                tempSum = newSum;
                result = num[index] + num[j] + num[k];
            }
            k--;
        }


Haaang on.

I think you can unduplicate your code here:

        else {
            if( newSum &lt; tempSum ) {
                tempSum = newSum;
                result = num[index] + num[j] + num[k];
            }
            if(num[index] + num[j] + num[k] &lt; target){
                k--;
            } else {
                j++;
            }
        }


Combine it with the idea of making the sum variable and you get the following: 

        int sum = num[index] + num[j] + num[k];
        if( sum == 0 ) {
            return sum;
        }
        else {
            int newSum = Math.abs( target - sum );                
            if( newSum &lt; tempSum ) {
                tempSum = newSum;
                result = sum;
            }
            if(sum &lt; target){
                k--;
            } else {
                j++;
            }
        }


Additionally, Math.abs is not yet required for your first if. So leaving that one out until it's needed speeds things up a bit.

And since a return statement exits the function, we can use an implicit else:

        int sum = num[index] + num[j] + num[k];
        if( sum == 0 ) {
            return sum;
        }
        int newSum = Math.abs( target - sum );                
        if( newSum &lt; tempSum ) {
            tempSum = newSum;
            result = sum;
        }
        if(sum &lt; target){
            k--;
        } else {
            j++;
        }