16. 最接近的三数之和

题目描述

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

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

示例 2：

输入：nums = [0,0,0], target = 1
输出：0

提示：

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

题解

排序 + 双指针

解题思路同 15. 三数之和。

class Solution {
public:
  int threeSumClosest(std::vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int dis = INT_MAX;
    for (int i = 0; i < nums.size() - 2; i++) {
      if (i > 0 && nums[i] == nums[i - 1]) continue;
      int m = i + 1, n = nums.size() - 1;
      while (m < n) {
        int sum = nums[i]+nums[m]+nums[n];
        if (sum == target) {
          return target;
        } else if (sum < target) {
          if (abs(target - sum) < abs(dis)) dis = target - sum;
          int x = nums[m];
          while(x == nums[++m] && m < n);
        } else {
          if (abs(target - sum) < abs(dis)) dis = target - sum;
          int x = nums[n];
          while(x == nums[--n] && m < n);
        }
      }
    }
    return target - dis;
  }
};

总结

1. 使用 INT_MAX 初始化三元组和与 target 的差值，然后在遍历过程中不断更新这个差值；
2. 三元组与 target 的插值 dis 类型为 int，存储真实差值，避免正负差异，dis = target - sum；
3. 与 target 最接近的和即为 target - dis；
4. 当 sum == target 时，直接返回 target，可以降低耗时，避免冗余枚举；