LeetCode 16. 最接近的三数之和

约 5 分钟
文章信息 14 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 50-100 腾讯 字节 阿里 华为 美团 拼多多 快手 虾皮
标签
数组 排序 双指针

题目描述

✅ 16. 最接近的三数之和

image-20260928194425549

题意分析

从数组中选择三个不同下标，使三数之和与 target 的绝对差最小，返回这三个数的和。三个位置上的值可以相等，但同一个下标不能重复使用；选择的元素也不要求连续。

目标是最接近，不要求恰好等于 target，也不要求返回所有三元组。数组至少有三个元素，题目保证最接近的答案唯一；应同时考虑偏小和偏大的和，统一按绝对差比较。

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

核心思路

[!blue]

直接枚举三个下标需要立方时间。先排序，再枚举三元组中下标最小的位置 i，其余两项就在 [i + 1, n - 1] 中用左右指针寻找。排序不会改变可选择的数值组合，却使指针移动对三数和的影响确定下来。

维护 ans 为已经检查过的最接近之和。每次得到 sum，先比较 abs(sum - target) 与 abs(ans - target)，再决定移动方向；即使当前和无法恰好命中目标，也可能是最终答案，不能直接跳过。

若 sum < target，固定 i 和当前 left 时，把 right 向左移动只会让和更小或不变，绝对差不会优于当前候选。当前候选已经记录，所以可以排除所有保留这个 left 的剩余组合，执行 left++。

若 sum > target，固定当前 right 时，更靠右的 left 只会让和更大或不变，同样不会更优，因此执行 right--。若 sum == target，绝对差已达到最小的零，直接返回即可。

每次都只排除不优于已检查候选的组合，固定 i 的扫描就不会漏掉更近的答案。最后遍历所有可能的 i，得到全局最优值；用前三个数之和初始化 ans，保证答案始终来自真实存在的三元组。

解题步骤

  • 先排序，并用前三个数之和初始化 ans，保证初值一定来自合法三元组。
  • 枚举第一个下标 i，令 left = i + 1、right = n - 1。
  • 计算 sum，先比较 |sum - target| 与 |ans - target|，更近就更新 ans。
  • sum < target 时右移 left；sum > target 时左移 right；相等则直接返回。
  • 当前左右指针相遇后，继续枚举下一个 i；所有位置枚举完后返回 ans。

代码实现

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;
    }
}

import "sort"

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)$。

关键点总结

[!green]

  • 排序提供单调性，指针移动才有明确方向。
  • 每个候选和都要先参与绝对差比较，再移动指针。
  • 答案应初始化为合法三数和，不能用可能不存在的 0。
  • 本题只返回一个和，无需像「三数之和」那样为结果集去重。

易错点总结

[!yellow]

  • 忘记取绝对值：直接比较 sum - target 会偏向更小的负差值，无法表示离目标的远近。
  • 返回了最小差值：差值只用于比较优劣，最终返回的是产生该差值的三数和。
  • 初值不是合法候选：不能随意令 ans = 0，因为数组未必能组成零，后续候选也未必会替换这个错误初值。
  • 同时移动两个指针：会漏解；当前和偏大只能排除 right，偏小只能排除 left。
  • 循环条件写成 left <= right：left == right 时会重复使用同一下标，必须写 left < right。

相似题目

题目 难度 关联与区别
15. 三数之和 中等 同样排序后固定一项并对撞指针，原题只收集和为0的组合，本题持续更新与目标的最小差。
18. 四数之和 中等 同样利用有序双指针，原题固定更多前缀元素并要求精确目标和。
259. 较小的三数之和 中等 排序后固定部分元素，再用左右指针收缩候选；本题根据与目标的距离更新最接近的和，该题满足阈值时批量累计指针对数。
611. 有效三角形的个数 中等 排序后固定部分元素，再用左右指针收缩候选；本题根据与目标的距离更新最接近的和，该题把三角不等式转为两数和比较。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/93653913
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！