题目链接：16.最接近的三数之和

题解：

嗯，也是双指针，和LeetCode的第15题（也就是我的上一篇文章的题解基本类似）。

题目简述：

上一题求三数字和为0， 这一题求三数之和最接近！

题解：

和上一题类似，求为0的三元组每次只有一种情况，即nums[i] + nums[j] + nums[k]

但是求最接近则有两种（左和右）：nums[i] + nums[j] + nums[k] - target，nums[i] + nums[j] + nums[k + 1] - target

思路是一样的，同样是双指针！思路见上一篇题解，即第15题 三数之和！

本题此题不需要去重，最终结果也只有一个！

同样需要排序！

不同之处：

  • nums[i] + nums[j] + nums[k] > target时，就k--，找到最接近的位置
  • 若k + 1没有超界，则计算一下nums[i] + nums[j] + nums[k + 1]的情况（右边）
  • 还有左边的情况（一定不会超界）
  • 使用minv更新与目标值相差最小的差值，即最接近值，若minv发生了更新，则更新res的值为差值较小的一方。

初始值minv，t1，t2都初始化为极大值INT_MAX。

注意： 差值计算需要使用绝对值abs()，同样while内的条件j < k - 1也得保证k--不会越界。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int res = 0, minv = INT_MAX;
        for(int i = 0; i < nums.size(); i++){
            for(int j = i + 1, k = nums.size() - 1; j < k; j++){
                while(j < k - 1 && nums[i] + nums[j] + nums[k] > target) k--;
                int t1 = INT_MAX, t2 = INT_MAX;

                t1 = abs(nums[i] + nums[j] + nums[k] - target);
                if(k + 1 < nums.size()) t2 = abs(nums[i] + nums[j] + nums[k + 1] - target);
                
                if(minv > min(t1, t2)){
                    minv = t1 < t2 ? t1 : t2;
                    res = t1 < t2 ? nums[i] + nums[j] + nums[k] : nums[i] + nums[j] + nums[k + 1];
                }
            }
        }
        return res;
    }
};