# 0016. 3Sum Closest
###### tags: `Leetcode` `双指针`
Link: https://leetcode.com/problems/3sum-closest/
## 思路
O(n^2)
固定一个 另外两个双指针
## Code

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int diff = INT_MAX;
        for(int i = 0;i < nums.size()-1&&diff!=0;i++){
            int l = i+1;
            int r = nums.size()-1;
            while(l!=r){
                int sum = nums[i]+nums[l]+nums[r]; 
                if(abs(sum - target)<abs(diff)){
                    diff = sum - target;
                }
                if(sum>target){
                    r--;
                }
                else{
                    l++;
                }
            }
        }
        return diff+target;
    }
};

## 注意
1.如果在第一个loop，判断条件那里没有加diff！=0，那么时间上只会beat掉50%的人，但是如果加了，则可以beat掉99%的人，说明如果有可以早点结束loop的条件还是要加上
2.原本想到的双指针是i在中间，l和r在两边，但是这就会要解决l或r跟i重合的问题，因此最后的做法是i在最左边，lr都在i的右边

## Code in Java

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        Arrays.sort(nums);
        int closestSum;
        // closestSum初始值为多少？
        closestSum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < len-2; i++){
            // 当全为负数时，此判断条件不可用，如何优化？
            // if (nums[i] > target) break;
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int left = i + 1;
            int right = len - 1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(sum - target) < Math.abs(closestSum - target)){
                    closestSum = sum;
                    while(left < right && nums[left] == nums[left + 1]) left++;
                    while(left < right && nums[right] == nums[right - 1]) right--;
                }
                if (sum > target){
                    right--;    
                }else if (sum < target){
                    left++;
                }else{
                    return closestSum;
                }
            }

        }
        return closestSum;
    }
}

## 心得
我觉得这题可以参考上一题，如果有重复的数很多，那么下边的代码是很有必要的

while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right--;

此外，还有一个是进入第一个loop时，怎么判断是不是还有必要继续

for (int i = 0; i < len-2; i++){
    // 当全为负数时，此判断条件不可用，如何优化？
    // if (nums[i] > target) break;

最后，初始值设定为$INT\_MAX$还是我这样？有没有什么trick

// closestSum初始值为多少？
closestSum = nums[0] + nums[1] + nums[2];