16. 最接近的三数之和

题目

• 题号：16
• 难度：中等
• https://leetcode-cn.com/problems/3sum-closest/

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

示例1

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

实现

首先可以发现该题与Leetcode第15题“三数之和”类似（解题笔记如下）。
语雀内容
因此也可以用排序+双指针的思路去解决。

思路1 排序+双指针

类似的，第一重循环遍历第一个数a，剩下两个数b和c的和要最接近target-a。
接着如果数组中的数字都是乱序的，那我们必须使用两重循环来枚举所有可能。因此我们需要对数组进行排序，这样第二重循环就可以从a所在的位置到数组的尾部之间（即[a+1, size)）枚举。
然后与第15题一样使用双指针替代第三重循环，降低复杂度。并用第11题“盛最多水的容器”的思路来移动双指针，即根据b，c与target关系决定移动b还是c的指针：

• 当b+c>target-a时，往左移动c的指针

• 当b+c<target-a时，往右移动b的指针

  class Solution {
  public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int best = 1e7;
        for(int a = 0; a<n; a++){
            if(a>0 && nums[a]==nums[a-1]){
                continue;
            }
            int b = a+1, c = n-1;
            while(b<c){
                int sum = nums[a] + nums[b] + nums[c];
                if(sum == target){
                    return sum;
                }
                if(abs(sum-target) < abs(best-target)){
                    best = sum;
                }
                if(sum < target){
                    // 移动b指针到下一个不相等的数
                    // 这里b+1<c是防止数组为[1,1,1,1]时会超过数组边界
                    while(b+1<c && nums[b]==nums[b+1]){
                        b++;
                    }
                    b++;
                } else{
                    // 移动c指针到下一个不相等的数
                    while(c-1>b && nums[c]==nums[c-1]){
                        c--;
                    }
                    c--;
                }
            }
        }
        return best;
    }
  };