59.3Sum Closest

1.Description(Medium)

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.

Notice

You may assume that each input would have exactly one solution.

Example

For example, given arrayS=[-1 2 1 -4], and target =1. The sum that is closest to the target is2.(-1 + 2 + 1 = 2).

Challenge

O(n^2) time, O(1) extra space

2.Code

3sum问题的变种。一样的遍历每个数，对剩余数组进行双指针扫描。区别仅仅在于当：

sum = A[left] + A[right]

(1) sum = target时直接返回

(2) sum != target时，在相应移动left/right指针之前，先计算abs(sum-target)的值，并更新结果。

 public int threeSumClosest(int[] numbers, int target) {
        if(numbers==null || numbers.length<3){
            return 0;
        }
        Arrays.sort(numbers);
        int mindiff=Integer.MAX_VALUE;
        for(int i=0;i<numbers.length-2;i++){
            int left=i+1;
            int right=numbers.length-1;
            while(left<right){
                //这里diff用sum-target,之后返回的时候直接返回target+diff即可。
                int sum=numbers[left]+numbers[right]+numbers[i];
                int diff=sum-target;
                //这样的话diff的正负就不对了
                //mindiff=Math.min(mindiff, Math.abs(diff));
                //正确的写法是：
                if(Math.abs(diff)<Math.abs(mindiff)){
                    mindiff=diff;
                }

                if(diff==0){
                    return target;
                }
                else if(diff<0){
                    left++;
                }else{
                    right--;
                }
            }           
        }
        return target+mindiff;
    }