最接近的三数之和

题目地址

1.思路

第一步很容易想到的就是降维处理，三个数相当于三维，那么我确定一个数的时候只剩下2维，这样就把问题转化为了两数之和，然后在确定一个数，这个时候就是一个数的比较就比较简单了
随即就想到怎么确定第一个数？

1.暴力法：

遍历整个数组元素，确定第一个数，依次类推可以得到其他维度的数，但是这个算法的时间复杂度是O(n^3),过于高了，在处理数组长度低的情况下还可以处理，但是位数一高就超时

image.png

2.双指针法：

既然暴力法不行那么就得换种思路，首先如果是二数找和的相似应该很好做
就是在一个排好序的数组里面用双指针进行检索

image.png

如果和比较大就让右边的指针左移，如果和比较小就让左边的指针右移，那么这个过程可以应用于2个数，其实3数之和确定一个数就变成了上面的情况，那么怎么确定一个数呢？
我们还是用循环的策略，但是这个循环必须在两边进行，也就是说每次循环必须从0开始或者从nums.length开始，这样就保证了剩下的两个数是可以按照上面的策略进行循环的，

image.png
如果先确定中间将无法保证每次循环都是一个新的数组，其中的某些数组会重复，效率降低

2.代码

public int threeSumClosest(int[] nums, int target) {
        int reminder = Integer.MAX_VALUE,temp=0;
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            int j=i+1,k=nums.length-1;
            while(j<k){
                int threeAddSum = nums[i]+nums[j]+nums[k];
                if(Math.abs(threeAddSum-target)==0){
                    return target;
                }
                if(Math.abs(threeAddSum-target)<reminder){
                    reminder = Math.abs(threeAddSum-target);
                    temp = threeAddSum;
                }
                if(threeAddSum>target){
                    k--;
                }
                if(threeAddSum<target){
                    j++;
                }

            }
        }
        return temp;
    }