LeetCode 16. 最接近的三数之和

LeetCode 16. 最接近的三数之和

思路：
用pair存两个关键元素，三个数与target差的绝对值和三个数的和，用pair存的好处是比较的时候按照第一个位置进行对比。
大概的思路与三数之和类似，在进行双指针操作的时候，最后还要判断一下在target的左侧的值，即三数之和是最后一个小于target的三个数。

代码：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        pair<int,int> res = make_pair(INT_MAX,INT_MAX);
        int n = nums.size();
        sort(nums.begin(),nums.end());

        for(int i = 0; i < n; i++){
            if(i && nums[i] == nums[i - 1]) continue;
            for(int j = i + 1,k = nums.size() - 1; j < k; j++){
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;
                while(j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= target) k--;
                int sum = nums[i]+nums[j]+nums[k];
                res = min(res,make_pair(abs(sum- target),sum));
                //三数之和小于target
                if(j < k - 1) {
                    sum = nums[i]+nums[j]+nums[k - 1];
                    res = min(res,make_pair(abs(sum - target),sum));
                }
            }
        }
        return res.second;
    }
};