LeetCode 16. 最接近的三数之和

2026-07-27 HGNULB 约 5 分钟

文章信息 14 个分类 4 个标签

分类

LeetCode CodeTop 中等已解决已掌握 50-100 字节跳动美团阿里巴巴快手腾讯华为拼多多虾皮

题目描述

✅ 16. 最接近的三数之和

题意分析

从数组里选三个不同下标的数，使它们的和与 target 的距离最近，返回这个和本身——不是差值，也不是三元组。这一点要在动笔前确认清楚，返回值类型答错是低级失分。

题目保证「恰好存在一个解」，也就是不会出现两个不同的三数和与 target 距离相同的情况。这个保证免去了平局裁决的麻烦：只要维护「距离更小就替换」即可，不用考虑相同距离下取哪个。

约束上 n 至少为 3，所以任取前三个数一定是一个合法的候选；数值范围不大，三数相加不会溢出 int。「最接近」意味着比较的是绝对差，和可以比 target 大也可以比它小。

解法：排序后固定一数双指针收缩

核心思路

问题关键：暴力枚举三个下标需要 $O(n^3)$。固定第一个数后，问题就变成在剩余区间中找一对数，使三数和尽量接近 target。

为什么选排序 + 双指针：排序后，left 右移只会让和变大，right 左移只会让和变小。因此当前和偏小时移动 left，偏大时移动 right，每次都能排除一批不可能更优的组合，把两层枚举降为一次线性扫描。

不变量与正确性：ans 始终是已经计算过的三数和中最接近 target 的一个。若 sum < target，固定当前 left 时，任何更小的 right 得到的和都不超过 sum，只会离 target 更远，所以可以排除当前 left；sum > target 时同理可以排除当前 right。若 sum == target，距离已经为 0，直接返回。

解题步骤

先排序，并用前三个数之和初始化 ans，保证初值一定来自合法三元组。

枚举第一个下标 i，令 left = i + 1、right = n - 1。

计算 sum，先比较 |sum - target| 与 |ans - target|，更近就更新 ans。

sum < target 时右移 left；sum > target 时左移 right；相等则直接返回。

例如 [-1,2,1,-4] 排序为 [-4,-1,1,2]。固定 -1 时得到和 2，与目标 1 只差 1，最终返回 2。

代码实现

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(sum - target) < Math.abs(ans - target)) {
                    ans = sum;
                }
                if (sum == target) {
                    return target;
                }
                if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return ans;
    }
}

func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    ans := nums[0] + nums[1] + nums[2]

    for i := 0; i < len(nums)-2; i++ {
        left := i + 1
        right := len(nums) - 1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            if absInt(sum-target) < absInt(ans-target) {
                ans = sum
            }
            if sum == target {
                return target
            }
            if sum < target {
                left++
            } else {
                right--
            }
        }
    }

    return ans
}

func absInt(num int) int {
    if num < 0 {
        return -num
    }
    return num
}

复杂度分析

时间复杂度：$O(n^2)$。排序为 $O(n \log n)$，外层枚举配合内层双指针为 $O(n^2)$。

空间复杂度：双指针部分为 $O(1)$；若计入原地排序的调用栈，通常为 $O(\log n)$。

关键点总结

排序提供单调性，指针移动才有明确方向。

每个候选和都要先参与绝对差比较，再移动指针。

答案应初始化为合法三数和，不能用可能不存在的 0。

本题只返回一个和，无需像「三数之和」那样为结果集去重。

易错点总结

忘记取绝对值：sum - target 可能为负，不能直接比较大小；[-4,-1,1,2]、target = 1 会误判偏小的和更优。

返回了最小差值：题目要返回三数和。[-1,2,1,-4]、target = 1 的答案是 2，不是差值 1。

初值不是合法候选：ans = 0 会让 [1,1,1]、target = 0 错误返回数组无法组成的 0。

同时移动两个指针：会漏解；当前和偏大只能排除 right，偏小只能排除 left。

循环条件写成 left <= right：left == right 时会重复使用同一下标，必须写 left < right。

相似题目

题目	难度	考察点
15. 三数之和	中等	找和恰为零，需对三元组去重
18. 四数之和	中等	双指针外再套一层枚举，注意溢出
167. 两数之和 II - 输入有序数组	中等	已排序数组上的对撞指针原型
259. 较小的三数之和	中等	满足条件时按区间批量计数
611. 有效三角形的个数	中等	固定最大边、双指针统计合法对数
1099. 小于 K 的两数之和	简单	带上界约束下维护最接近的两数和
LCR 006. 两数之和 II - 输入有序数组	简单	167 的镜像题，返回下标约定不同
LCR 007. 三数之和	中等	15 的镜像题，练习去重模板
剑指 Offer 57. 和为s的两个数字	简单	有序数组找两数精确和，任返一组即可
面试题 16.24. 数对和	中等	枚举全部数对，元素只能使用一次