16.3Sum Closest

题目：

解析：

不同于上一题的求和为0的情况，这一题给定一个值，然后要找离他最近的解决方案，考虑还是先排序，然后遍历得到每种情况的sum结果，然后将结果和目标值相比较，把相减的绝对值比较小的一个保存下来。
题目中说考虑最佳解决方案只有一个，所以不用考虑多个情况。

思路：

先将数组升序排列，用第一重for循环确定第一个数字，
在第二重循环里面，第二、三个数字分别从两端往中间扫
如果三数之和=target,则直接返回target
如果三数之和>target,则把第三个数的指针往左移
如果三数之和<target,则把第二个数的指针往右移
时间复杂度：O(N^2)

代码：

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if(nums==null || nums.length<3) return 0; //数组长度小于三或者数组为空时，直接返回0
        //先排序
        Arrays.sort(nums);
        int len = nums.length;
        int dif=0;
        int min_dif = Integer.MAX_VALUE;  //最小差值
        int sum =0;
        int result = 0;
        for(int i =0;i<len-2;i++){
           int left = i+1;
           int right = len-1;
            while(left<right){
                sum = nums[i]+nums[left]+nums[right];//三数之和
                dif = Math.abs(sum-target);//差值的绝对值
                if(sum == target) return target; 
                if(dif<min_dif){
                    min_dif = dif;
                    result = sum;
                    
                }
                if(sum > target) right--;
                if(sum < target) left++;
            }
        }
        return result;
        
    }
}

后记：

这道题比15题简单多了，思路清晰即可。