最接近的三数之和

题目描述

给你一个长度为 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
解释：与 target 最接近的和是 0 (0 + 0 + 0 = 0)

约束条件

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

我的解题过程

方法一：排序 + 双指针

先对数组进行排序，然后依次固定一个数，使用双指针在剩下的数组中寻找两个数，使得三数之和最接近目标值。

function threeSumClosest(nums: number[], target: number): number {
  nums.sort((a, b) => a - b);
  let diff = Infinity;
  let sum = 0;

  for (let i = 0; i < nums.length - 2; i++) {
    let l = i + 1;
    let r = nums.length - 1;

    while (l < r) {
      const total = nums[i] + nums[l] + nums[r];
      const currentDiff = Math.abs(total - target);

      if (currentDiff < diff) {
        sum = total;
        diff = currentDiff;
      }

      if (total === target) return target;

      if (total > target) {
        r--;
      } else if (total < target) {
        l++;
      }
    }
  }

  return sum;
}

解题思路

核心逻辑：

这道题与「三数之和」类似，但目标是找到最接近 target 的三数之和，而不是找到和为 0 的三元组。关键点：

1. 先对数组排序，便于使用双指针
2. 固定第一个数 nums[i]，在 i 之后的数组中用双指针寻找另外两个数
3. 记录当前找到的最接近的和，通过比较差值的绝对值来更新
4. 如果找到和等于 target，直接返回（题目保证只有一个解）

算法步骤：

1. 对数组进行升序排序
2. 初始化变量：diff = Infinity（记录最小差值），sum = 0（记录最接近的和）
3. 遍历数组，固定第一个数 nums[i]（i 从 0 到 length-2）
4. 设置双指针：left = i+1，right = length-1
5. 当 left < right 时：
   • 计算三数之和 total = nums[i] + nums[left] + nums[right]
   • 计算与目标的差值 currentDiff = abs(total - target)
   • 如果 currentDiff < diff，更新 sum 和 diff
   • 如果 total == target，直接返回 target（找到精确匹配）
   • 如果 total > target，right--（和太大，需要减小）
   • 如果 total < target，left++（和太小，需要增大）
6. 返回记录的最接近的和 sum