leetcode No.16 3Sum Closest(最接近的

题干：

效果：

思路：

这道题跟No.15很像，就是要找三数之和，但15是找三数之和为0，这题是找离target最近的和。

首先我们得排序，因为调用默认排序的时间复杂度是O(nlogn)，而这道题暴力遍历是O(n^{3)，想处理三个数，至少也得是O(n}2)的复杂度，所以先给他排个序对时间复杂度不会有大的影响。

从小到大排完序后，前两个从前往后取，第三个从最后位置往前取，这样就有一个好处，我们把这三个数加起来，如果它超过target，那显然是因为数不够大，那就让中间那个数往后移动，如果小于target，那么就往前移动第三个数。

每次移动完后，记录最小的差值，最后循环结束返回最小的差值就行。

这里我一开始并没有bug free，因为三数之和与target值有两种接近方式，一种是>，一种是<，所以我就设了两个标识变量，哪个更接近就返回哪个，但是发现min_value是整数的最小值，而如果对它取绝对值，它就会溢出，然后变成1，而MAX_VALUE取反不会溢出，所以你们会看到我最后return时并没有用abs方式。

代码：

import java.util.Arrays;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        //先排序
        Arrays.sort(nums);
        //初始化最接近的值
        int closePlusMin=Integer.MAX_VALUE;
        int closeMinusMax = Integer.MIN_VALUE;
        for(int i=0;i<nums.length-2;i++){
            if(i==0||i>0&&nums[i-1]!=nums[i]){
                int low = i+1;
                int high = nums.length-1;
                while(low<high){
                    int sum = nums[low]+nums[high]+nums[i];
                    if(sum==target){
                        return target;
                    }
                    else if(sum<target){
                        low++;
                    }
                    else{
                        high--;
                    }
                    if(sum-target>0){
                        closePlusMin = Math.min(closePlusMin,sum-target);
                    }
                    else{
                        closeMinusMax = Math.max(closeMinusMax,sum-target);
                    }
                }
            }
        }
        return -closePlusMin>closeMinusMax?target+closePlusMin:target+closeMinusMax;
    }
}