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[i1]nums[i2]nums[i3] target等边界判断本题只求最接近 target 的那个和不需要枚举所有组合因此只需要维护一个当前最优差距即可。基于上述差异本题采用的解法是经典的排序 双指针夹逼two-pointer。解法一排序 双指针夹逼O(n²)算法流程对数组调用sort.Ints(nums)升序排序固定指针i从 0 扫描到n-3作为三元组中的第一个数去重循环中与前一位置比较若nums[i] nums[i-1]则continue把i移到下一个与前一个数字不同的位置因为相同首元素产生的候选和是等价的跳过可以避免冗余计算双指针j i1紧跟在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.gopackage 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 : i1, 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.MaxInt32diff初始化为int的最大值确保任何第一个合法组合都能刷新它。由于nums[i] nums[j] nums[k]在int范围内这个哨兵值安全可用外层循环上界是n-2i最多到n-3数组下标从 0 开始保证j i1与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 中提供了完整的表驱动测试覆盖了多种边界场景输入数组target期望输出覆盖点[-1, 0, 1, 1, 55]32多组近似解取最接近者[0, 0, 0]10全零数组[-1, 2, 1, -4]12题目官方示例[1, 1, -1]01含重复元素[0, 1, 2, 3]66sum target精确匹配触发提前返回分支[1, 1, 1, 0, 5]1007首元素重复触发nums[i] nums[i-1]跳过分支测试结构采用本仓库统一的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 -covermodeatomic -coverprofilecoverage.txt ./leetcode/...即可运行全部题解测试0016 目录下两个解法均达到 100% 覆盖。与同系列题目的对比总结维度15. 3Sum16. 3Sum Closest18. 4Sum输出所有和为 0 的三元组最接近 target 的一个和所有和为 target 的四元组核心难点去重逼近最优差距去重 剪枝提前终止无法提前终止sum target可提前返回无法提前终止复杂度O(n²)O(n²)O(n³)仓库实现15. 3Sum.go16. 3Sum Closest.go18. 4Sum.go三题共享排序 双指针的骨架但因输出形态不同在去重策略、提前退出条件和剪枝逻辑上各有差异。理解了这三题的异同就掌握了「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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考