[016] 最接近的三数之和 (3Sum Closest)

难度：中等 | 标签：数组、双指针、排序

题目描述

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个在 不同下标位置 的整数，使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。

示例 1：

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

解法：排序 + 双指针 (Sorting + Two Pointers) —— 推荐 ✅

这道题与 015. 三数之和 的核心逻辑完全一致：

1. 排序：保证数组有序，这是双指针调整大小的前提。
2. 固定一位：遍历 i 作为第一个加数。
3. 双指针逼近：使用 left 和 right 在两端寻找另外两个数。

与「三数之和」的区别：

• 不需要去重（题目只要求返回一个和，不要求返回所有组合）。
• 需要维护一个全局变量 res，记录当前最接近 target 的那个和。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        // 初始化 res：先随便取前三个数的和作为“基准”
        int res = nums[0] + nums[1] + nums[2];
        
        for(int i = 0; i < n; i++) {
            int left = i + 1;
            int right = n - 1;
            
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                // 1. 比较并更新最接近的值
                // 如果当前 sum 与 target 的距离，比之前记录的更近，就更新 res
                if(abs(target - sum) < abs(target - res)) {
                    res = sum;
                }
                
                // 2. 根据大小移动指针 (类似二分查找的逻辑)
                if(sum > target) {
                    right--; // 和太大了，右指针左移，让和变小
                }
                else if(sum < target) {
                    left++;  // 和太小了，左指针右移，让和变大
                }
                else {
                    return sum; // 距离为0，肯定是最近的，直接返回
                }
            }
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：。排序耗时 ，双指针遍历耗时 。

• 空间复杂度：。

易错点分析

1. 盲目移动指针：

   不能在 while 循环里无条件地写 left++ 和 right--。必须根据 sum 与 target 的大小关系来决定移动哪一个。

2. 初始化问题：

   res 最好直接初始化为数组前三个元素之和 (nums[0] + nums[1] + nums[2])。如果初始化为 INT_MAX，在计算 abs(target - res) 时可能会溢出。

3. 绝对值比较：

   判断“谁更接近”时，一定要用 abs() 取绝对值，因为差值可能是负数。