16. 最接近的三数之和（中等）

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

示例：

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

思路：排序+双指针

借鉴15题中的双指针思路，本题中只需要确定一个最优的答案，然后将其返回即可。因此，本题不需要排除重复答案，也不需要找到所有的最优组合。

• 排序： 先将给定 nums 排序，复杂度为 O(NlogN)。
• 双指针思路： 固定 3 个指针，最小数字的指针 k，双指针 i，j 分设在数组索引(k, len(nums))两端，通过双指针交替向中间移动，记录对于每个k、i、j的和 nums[k] + nums[i] + nums[j] == s 的大小与target的关系：
  • 设置变量c用来记录前面组合中，s与target的最小差值的数额
  • 当 s==target时，k、i、j所对应的三个数的和与target最接近，target为最优解直接返回即可；
  • 当 s>target时，判断s-target与c的大小关系，若更小，则需要更新res=s和c=s-target.否则，无需更新。最后更新j--；
  • 当 s<target时，判断target-s与c的大小关系，若更小，则需要更新res=s和c=target-s.否则，无需更新。最后更新i++；

(1) C++

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int m = nums.size();
        sort(nums.begin(),nums.end());
        int c = INT_MAX;
        int res = 0;
        if(m<3) return 0;
        for(int k=0;k<m-2;k++){
            int i=k+1 , j=m-1;
            while(i<j){
                int s =nums[k]+nums[i]+nums[j];
                if(s == target ){
                    return target;
                }
                else if(s > target){
                    if(s-target<c){
                        res = s;
                        c = s-target;
                    }
                    j--;
                }
                else{
                    if(target-s <c){
                        res = s;
                        c = target-s;
                    }
                    i++;
                }
                
            }
        }
        return res;
    }
};

(2) python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        res = 0
        c = inf
        m = len(nums)
        nums.sort()
        for k in range(m-2):
            i = k+1
            j = m-1
            while(i<j):
                s = nums[k]+nums[i]+nums[j]
                if s==target:
                    return target
                elif s > target:
                    if(s-target<c):
                        res = s
                        c = s-target
                    j-=1
                else:
                    if(target-s < c):
                        res = s
                        c = target -s
                    i+=1
        return res