题目内容

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

题解

继续采用双指针做法来做本题。首先，固定i，对于每个j，找出一个最小值k使得，nums[i] + nums[j] + nums[k] >= target。

又因为只要找出来nums[i] + nums[j] + nums[k] >= target，那么必然nums[i] + nums[j] + nums[k-1] < target。
这样的话，就可以比较一下哪个更加接近，最终确定答案。

这里面需要对pair这个数据结构进行一个复习，解释地址为：https://blog.csdn.net/u011499425/article/details/52756088

代码

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        pair<int,int> res(INT_MAX,INT_MAX);
        sort(nums.begin(),nums.end());
        for(int i = 0;i < nums.size(); i++)
            for(int j = i + 1,k = nums.size() - 1; j < k; j++){
                while(k - 1 > j && 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));
                if(k - 1 > j){
                    sum = nums[i] + nums[j] + nums[k - 1];
                    res = min(res, make_pair(target - sum,sum));
                }
            }

        return res.second;
    }
};