企业官网建设流程全解析

LeetCode-Go 题解精讲：16. 3Sum Closest 最接近的三数之和（双指针夹逼 + 暴力解法）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文以 LeetCode 第 16 题「3Sum Closest（最接近的三数之和）」为核心，结合 LeetCode-Go 仓库中 0016.3Sum-Closest 目录下的完整源码与单元测试，深入讲解"排序 + 双指针夹逼"这一 O(n²) 解法的推导过程与实现细节，并给出 O(n³) 暴力解法作为对照。读完本文，你将掌握如何在有序数组中用双指针快速逼近任意目标值、如何处理重复元素、以及该题与第 15 题（3Sum）、第 18 题（4Sum）在思路上的本质差异。

问题描述

给定一个长度为n的整数数组nums和一个整数target，要求找出数组中的三个整数，使得它们的和最接近target，返回这三个整数的和。题目保证每个输入恰好只有一个解。

官方示例：

Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

注意本题与 15. 3Sum 的关键差异：第 15 题要求返回所有和为 0 的三元组（结果集），而本题只要求返回一个最接近目标值的和（标量），且输入保证有唯一解。因此本题不需要收集全部组合，一旦找到sum == target的精确匹配即可提前终止。

解题思路：为什么不能照搬 3Sum / 4Sum 的做法

乍一看，本题与第 15 题（三数之和）和第 18 题（四数之和）非常相似，都是"求若干个数之和"的系列问题，但本题的做法与 15、18 题完全不同：

• 15 题要求输出所有a + b + c = 0的三元组集合，核心难点是去重，所以 15. 3Sum.go 中不仅要移动双指针，还要在左右指针移动时跳过重复值，避免输出重复组合；
• 18 题要求输出所有a + b + c + d = target的四元组集合，18. 4Sum.go 在双指针之外还增加了剪枝优化（nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <= target等边界判断）；
• 本题只求最接近 target 的那个和，不需要枚举所有组合，因此只需要维护一个"当前最优差距"即可。

基于上述差异，本题采用的解法是经典的排序 + 双指针夹逼（two-pointer）。

解法一：排序 + 双指针夹逼（O(n²)）

算法流程

1. 对数组调用sort.Ints(nums)升序排序；
2. 固定指针i从 0 扫描到n-3，作为三元组中的第一个数；
3. 去重：循环中与前一位置比较，若nums[i] == nums[i-1]则continue，把i移到下一个与前一个数字不同的位置（因为相同首元素产生的候选和是等价的，跳过可以避免冗余计算）；
4. 双指针j = i+1（紧跟在i之后）、k = n-1（数组末尾）从两端向内夹逼：
   • 计算sum = nums[i] + nums[j] + nums[k]；
   • 若abs(sum - target) < diff，更新当前最优结果res与最小差距diff；
   • 若sum == target，直接返回（这是理论最优，差距为 0，不可能更近）；
   • 若sum > target，说明和偏大，k--让较大的数变小；
   • 若sum < target，说明和偏小，j++让较小的数变大。

由于数组已排序，nums[k]是当前范围内最大的数，j后移、k前移的移动策略保证了每次移动都是朝着缩小与target差距的方向进行，直到j >= k收敛。

仓库中的完整实现

源码位于 16. 3Sum Closest.go：

package leetcode import ( "math" "sort" ) // 解法一 O(n^2) func threeSumClosest(nums []int, target int) int { n, res, diff := len(nums), 0, math.MaxInt32 if n > 2 { sort.Ints(nums) for i := 0; i < n-2; i++ { if i > 0 && nums[i] == nums[i-1] { continue } for j, k := i+1, n-1; j < k; { sum := nums[i] + nums[j] + nums[k] if abs(sum-target) < diff { res, diff = sum, abs(sum-target) } if sum == target { return res } else if sum > target { k-- } else { j++ } } } } return res }

关键实现细节剖析

• 初始差距用math.MaxInt32：diff初始化为int的最大值，确保任何第一个合法组合都能刷新它。由于nums[i] + nums[j] + nums[k]在int范围内，这个哨兵值安全可用；
• 外层循环上界是n-2：i最多到n-3（数组下标从 0 开始），保证j = i+1与k = n-1始终能构成合法三元组，i < n-2即i <= n-3；
• 提前返回优化：当sum == target时差距为 0，任何其他组合都不可能更接近，直接返回res即可；
• n <= 2的边界：代码外层用if n > 2保护，数组长度不足 3 时返回res的零值 0，保证函数不会越界访问。

辅助函数abs用于计算整数的绝对值（注意题目约束保证和与target的差不会溢出）：

func abs(a int) int { if a > 0 { return a } return -a }

复杂度分析

• 时间复杂度 O(n²)：排序为 O(n log n)，外层循环 O(n)，内层双指针每轮至多移动 O(n) 次，总体 O(n²)；
• 空间复杂度 O(1)：除排序外仅使用常数个变量（sort.Ints为原地排序）。

解法二：暴力三重循环（O(n³)）

作为对照，仓库中还提供了最直观的暴力解法threeSumClosest1，枚举所有下标组合(i, j, k)，三重循环逐一计算nums[i] + nums[j] + nums[k]与target的差距，并记录差距最小的那个和：

// 解法二 暴力解法 O(n^3) func threeSumClosest1(nums []int, target int) int { res, difference := 0, math.MaxInt16 for i := 0; i < len(nums); i++ { for j := i + 1; j < len(nums); j++ { for k := j + 1; k < len(nums); k++ { if abs(nums[i]+nums[j]+nums[k]-target) < difference { difference = abs(nums[i] + nums[j] + nums[k] - target) res = nums[i] + nums[j] + nums[k] } } } } return res }

暴力解法不需要排序、不需要去重，逻辑简单不易出错，但时间复杂度为 O(n³)，当n较大时无法通过全部用例。它更适合作为正确性参照：在仓库的测试中，两个解法被同时验证，确保双指针优化版的输出与暴力版一致。

单元测试：用测试用例印证算法行为

仓库在 16. 3Sum Closest_test.go 中提供了完整的表驱动测试，覆盖了多种边界场景：

测试结构采用本仓库统一的question16 / para16 / ans16表驱动模式，每个用例都会同时跑两个解法并断言结果一致：

if out != a.one { t.Fatalf("threeSumClosest(%v, %d) = %d, want %d", p.a, p.target, out, a.one) } if out2 := threeSumClosest1(append([]int{}, p.a...), p.target); out2 != a.one { t.Fatalf("threeSumClosest1(%v, %d) = %d, want %d", p.a, p.target, out2, a.one) }

其中append([]int{}, p.a...)的写法用于复制输入切片，避免两个解法共享底层数组互相影响。

在仓库根目录执行go test ./leetcode/...或通过 gotest.sh 脚本（go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...）即可运行全部题解测试，0016 目录下两个解法均达到 100% 覆盖。

与同系列题目的对比总结

三题共享"排序 + 双指针"的骨架，但因输出形态不同，在去重策略、提前退出条件和剪枝逻辑上各有差异。理解了这三题的异同，就掌握了「N 数之和」系列问题的通用套路：固定前 k-2 个数，用双指针夹逼剩余两数。

总结

• 3Sum Closest 的最优解是排序 + 双指针夹逼，时间复杂度 O(n²)、空间 O(1)，核心是维护(sum, diff)最优对，并通过sum与target的大小关系决定移动j还是k；
• 重复元素处理采用"i与前一位置比较、相等则跳过"的轻量方案，避免了用 map 计数去重的额外开销；
• 暴力三重循环 O(n³)作为正确性兜底实现，与双指针版在单元测试中交叉验证；
• 仓库为该题提供了覆盖精确匹配、重复元素、边界长度等场景的完整测试用例，是理解该算法行为的最佳参考。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go