力扣-16. 最接近的三数之和（3Sum Closest）

最后编辑于2025-06-25

16. 最接近的三数之和（3Sum Closest）

Medium

给定整数数组 nums（长度 n）和整数 target，从数组中找出三个整数，使它们之和最接近 target，返回这三个整数之和。题目保证答案唯一。

示例 1：

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

示例 2：

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

约束：

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

思路（排序 + 双指针）

本题与「三数之和」类似，经典做法依然是先对数组排序，然后固定一个数 nums[i]，在其后部分用左右双指针寻找最接近 target - nums[i] 的两数之和。核心步骤：

  1. 对 nums 排序，便于双指针线性移动。
  2. 维护当前最优解 closest（初始化为前三个数之和）和最小差值 diff = abs(closest - target)。
  3. 枚举第一个数 i（可跳过重复以略微优化），令 left = i+1, right = n-1，在 while 中计算 sum = nums[i] + nums[left] + nums[right]：
    • 若 abs(sum - target) < diff，更新 diff 与 closest。
    • 若 sum < target，左指针右移以增大和；若 sum > target，右指针左移以减小和；若 sum == target，则直接返回 target（最优）。
  4. 最终返回 closest。

时间复杂度 O(n^2)，空间复杂度 O(1)（忽略排序空间）。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int closest = nums[0] + nums[1] + nums[2];
        int diff = abs(closest - target);
        for (int i = 0; i < n - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 可选去重优化
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                int newDiff = abs(sum - target);
                if (newDiff < diff) {
                    diff = newDiff;
                    closest = sum;
                }
                if (sum < target) ++left;
                else if (sum > target) --right;
                else return target; // 精确命中
            }
        }
        return closest;
    }
};

作者想说的话：
和三数之和思路一致，但这里要关注差值的维护：每次计算三数之和后即时比较并更新最小绝对差，遇到恰好等于目标值可以提前返回。排序 + 双指针使得枚举复杂度降到 O(n^2)，足够应对题目约束。