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).

public int threeSumClosest(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int minDiff = Integer.MAX_VALUE;
        int bestSum = -1;
        Arrays.sort(num);
        for(int i=0;i<num.length;i++){
            int twoSum = findClosest(num,i,target);
            int sum = twoSum+num[i];
            if(Math.abs(sum-target)<minDiff){
                minDiff = Math.abs(sum-target);
                bestSum = sum;
            }
        }
        return bestSum;
    }

    public int findClosest(int[] num, int curr, int target){
        int newTarget = target-num[curr];
        int left = 0;
        if(left==curr){
            left++;
        }
        int right = num.length-1;
        if(right==curr){
            right--;
        }
        int minDiff = Integer.MAX_VALUE;
        int bestSum = -1;
        while(left<right){
            int sum = num[left]+num[right];
            if(sum==newTarget){
                return newTarget;
            }
            if(Math.abs(sum-newTarget)<minDiff){
                    minDiff = Math.abs(sum-newTarget);
                    bestSum = sum;
            }
            if(sum<newTarget){
                left++;
                if(left==curr){
                    left++;
                }
            }else{
                right--;
                if(right==curr){
                    right--;
                }
            }
        }
        return bestSum;
    }

The findClosest is a helper function which finds a pair of integers in the given array with the closest sum to the new target num. The new target number is target-num[curr]. Then in the main function, we only need to pick a number as the first integer among the three integers and then use this function to find the closest sum of the rest two integers.

We should first sort the array so that it only takes O(n) for findClosest each time. So the total running time is O(nlgn+n2) = O(n2).

Share