在力扣热题100的榜单里第16题最接近的三数之和一直被当成第15题三数之和的加长版来刷。名字像、参数像连题解模板都只要改两三行。但我自己刷完这道题之后发现如果只是照着15题的代码改几个符号你会漏掉这道题真正的价值——它把双指针和贪心揉在了一起值得单独拆开讲一遍。这篇文章我不会只贴一份能AC的代码而是把这题的完整思考链路走一遍暴力为什么不行排序双指针为什么行贪心移动为什么不会漏答案以及边界条件里那些一提交就报错的坑。你可以把它当成刷题笔记也可以当成面试前双指针专题的复习提纲。1. 从换皮题到送命题最接近的三数之和到底难在哪1.1 题目描述与两种刷题反应先把题目摆出来。给一个整数数组nums和一个目标值target要求从数组里选出三个整数使它们的和与target的差的绝对值最小返回这个和。注意这里不是返回三元组只返回那个最接近的和。就这么一句话刷题的人大概分两派。第一派刚刷完第15题三数之和看到这题会心一笑把等于target改成最接近target不就是把所有候选和都算一遍、维护最小差值吗第二派拿到题直接懵了等于是找组合那三数之和那套排序双指针还能用吗——能用但你要想清楚怎么用。我用换皮题来形容它是因为面试里它真的能区分两类人。一类人背模板改完代码能过但你问他指针为什么这样动他答不上来另一类人把模板背后的贪心逻辑看透了稍微一变题也能解。这篇文章想把大家往第二类推一把。1.2 暴力枚举先走一遍O(n³) 的复杂度到底能不能接受在谈双指针之前先把最朴素的做法写出来。很多同学觉得这种求最接近的题当然得枚举三个 for 循环套一起把所有组合算一遍挑离target最近的和返回。def threeSumClosest(nums, target): n len(nums) best float(inf) for i in range(n): for j in range(i 1, n): for k in range(j 1, n): s nums[i] nums[j] nums[k] if abs(s - target) abs(best - target): best s return best这段代码逻辑上完全正确时间复杂度 O(n³)。如果你在笔试里提交n 比较小的时候它甚至能过。但这道题在力扣上是中等难度数据范围给的 n 上限通常是 1000 甚至 3000O(n³) 在 3000 的规模下是 270 亿次运算再怎么剪枝也扛不住。那能不能稍微优化一下如果先对数组排序枚举i和j然后对k用二分查找可以把复杂度压到 O(n² log n)。排序本身 O(n log n)后面对每对(i, j)做一次二分是 O(log n)总复杂度 O(n² log n)。这个方案很多新手能想到也算是一个不错的过渡思路。但双指针方案能做到 O(n²)而且写起来比枚举两个二分第三个更简洁。关键思路是排序之后固定一个数i让left和right两个指针从i 1和n - 1两端向中间走。这里面的取舍逻辑就是这篇文章的核心。2. 排序双指针的主框架固定一个数剩下的交给左右指针2.1 排序为什么是必需的把无序问题变成有序搜索先回答一个很多人忽略的问题为什么这题要先排序第15题三数之和也用了排序它排序是为了配合双指针去重这题排序同样是为了让双指针成立但本质原因是排序给了数组一个单调性。有了单调性之后当你固定住i看当前三数之和s与target的关系时你可以确定下一步应该往哪个方向走s偏小就找更大的数s偏大就找更小的数。而更大/更小在排序数组里对应的是指针往右/往左移动。如果没有排序数组元素大小是跳跃的同样的一次比较结果你完全不知道是该试下一个元素还是跳过好几个元素也就谈不上收敛。打个不精确的比方你在一条直线上找目标点身边的人都告诉你目标在左边还是右边你每次都能排除一半方向自然走得快如果身边的人位置是乱的告诉你目标大概在那个方向也没用因为你不知道哪个方向才是更近的。所以这道题的第一步永远是nums.sort()。排序这个动作本身不改变答案——三个数的和与它们在数组里的顺序无关这就给了我们安全排序的前提。2.2 核心实现Python 代码逐行拆解直接上代码这是我提交过、也拿来讲过很多次的版本from typing import List class Solution: def threeSumClosest(self, nums: List[int], target: int) - int: nums.sort() n len(nums) best nums[0] nums[1] nums[2] for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: s nums[i] nums[left] nums[right] if s target: return s if abs(s - target) abs(best - target): best s if s target: left 1 else: right - 1 return best逐行说几个关键点。第一best初始化为排序后前三个元素之和。后面会专门讲为什么这样取比float(inf)更稳这里先记住这个写法。第二外层循环i从 0 到n - 3。i每固定一次问题就退化成在i右侧的有序区间里找两个数使nums[i]加两数之和最接近target。这一步其实把三数之和降维成了两数之和最接近版。第三内层 while 循环里每次计算s如果差值为 0 直接返回——因为不可能有比 0 更小的差值了。这就是天然的剪枝也是这道题里最爽的一行除了最坏情况运气好可以提前结束。第四也是最关键的当s ! target时先用一个if判断差值是否刷新best然后根据s与target的大小关系决定移动left还是right。这两行的顺序不能反先更新答案再移动指针因为移动之后当前组合就不存在了。2.3 指针移动的贪心方向差值符号决定取舍这里详细说说那个if s target: left 1 else: right - 1到底在干什么。固定i之后区间[left, right]是有序的。s是当前三数之和。如果s等于target直接结束。如果s小于target说明现在三个数的和差一点还差一个正数才能到target。我们要把和变大只有两个选择left右移取更大的数或right左移取更小的数。right左移会让和更小明显偏离target所以在s target的情况下应该让left右移。反过来s大于target时要让和缩小应该让right左移。left右移会让和更大只会更远。这就是贪心在这道题里的具体形态每一步都根据当前信息选择一个让结果更可能接近target的移动方向。你可能会问万一left右移之后后面的组合都偏大还不如刚才这个偏小的组合呢——那也没关系因为我们在移动前已经把当前组合的差值记录到best里了错过不了。这个一边记录、一边逼近的思路正是双指针解这类题的灵魂。我有个小口诀小了动左边大了动右边等于就回家。给团队讲的时候这个口诀帮不少人记住了代码但真要理解还是得看下一章的正确性推导。3. 贪心正确性推导为什么左移/右移永远不会错过最优解3.1 有序数组带来的单调性一切收敛的基础理解了代码之后更要紧的问题是凭什么每次朝一个方向挪指针最后得到的best一定是全局最优解这需要用到排序数组的一个基本性质——单调性。固定i之后看区间[left, right]。如果left固定随着right不断左移nums[right]单调不增所以三数之和s单调不增。如果right固定随着left不断右移nums[left]单调不减所以s单调不减。这个单调性听起来很基础但它是整个贪心能够成立的基石。因为s关于left和right的变化是可预测的往一个方向移动结果只会朝确定的方向变。有了这种可预测性我们才能在当前状态判断哪个方向更可能有戏。3.2 排除法证明丢掉某个指针为什么是安全的现在我们做一个严格的排除论证这是这道题最精华的部分。假设当前s target。因为数组单调不减固定right时如果把当前left保留下来、把right往左移得到的所有和s都会满足s ≤ s target。关键在这里既然s ≤ s target那么s和target的距离一定小于s和target的距离。也就是说当前left配合任何更小的right都不可能比当前组合更接近target。既然当前组合已经尝试并记录过了那么当前的left就没有利用价值了可以放心地left 1把这个左指针丢掉。反过来当s target时如果把right保留下来、让left右移得到的所有s都满足s ≥ s target距离只会更远而不是更近。所以当前right也没有留下来的必要right - 1是安全的。这个论证用到的其实就是一个排除法每一步移动后被丢掉的指针与区间内任意元素的组合都不可能优于已经记录过的解。因为排序保证的方向性我们丢弃的是一个确定没希望的方向而不是碰运气。这就是为什么双指针在这类题目上是不重不漏的。跟冒泡排序那种两两比较交换不一样双指针不是通过比较一次就把所有候选都算一遍而是利用排序后的单调性把不可能成为最优解的候选成片地排除掉。每一轮循环排除一条边整体复杂度才从 O(n³) 降到 O(n²)。3.3 打靶类比与二分搜索的区别为了更直观我习惯把这道题想象成打靶。靶心是target你有一发子弹目标是打出最小的偏差。现在你有两个旋钮left控制低端弹药right控制高端弹药。一开始把left放在最小、right放在最大。如果当前这一发的落点偏左s target那说明问题出在低端弹药太小你需要把left往右拨换取更大的落点如果偏右就把right往左拨。每一轮你拨动一个旋钮落点都在朝靶心收拢。这个图景和二分搜索有点像但要注意区别二分搜索是区间减半、目标值在寻找一个精确点这道题是区间收缩、目标值是逼近一个最优和。它们的共同点是都依赖有序性不同点是二分搜索每一步可以直接砍掉一半空间而双指针每一轮只移动一个位置收缩的粒度更小也因此能适应最接近这种比精确相等更宽松的要求。如果你在面试里被问到这题把这段为什么敢贪心的论证讲出来面试官一般就会点头了。很多人只背代码问到这里就卡壳非常可惜。4. 那些一提交就暴露的边界细节4.1 初始答案取前三项和而不是取无穷大先说说best的初始化。我见过不少写法是best float(inf)因为这样第一个候选一定可以更新best。你会发现虽然代码能过但在裸写代码时可读性差一些而且从直觉来说直接取排序后前三项之和更自然——它本身就是一个合法的三数之和后续的if abs(s - target) abs(best - target)比较也能正常进行。为什么取前三项是安全的因为题目保证数组长度至少为 3排序之后nums[0] nums[1] nums[2]一定存在。假设target是正数、数组全是负数前三项和可能是负数这也没关系best只是一个当前已知最好不一定是最优后续会不断更新。还有一个小细节如果数组长度恰好是 3外层循环i只会执行一次i 0内层 while 也只跑一次返回的就是这个 sum。所以边界上不用额外判断长度小于 3 的情况——当然严谨的代码可以在开头加一个if len(nums) 3: return 0之类的保护面试时会显得更细心。4.2 重复元素要不要跳过这里和三数之和不同第15题三数之和要求返回三元组遇到重复元素必须跳过否则结果里会出现重复组合。但第16题只返回最接近的和不要求返回具体是哪三个数。这种情况下跳过重复元素严格来说不是必需的——就算有重复计算出来的和是同一个差值也一样best不会变错。那为什么我的代码里还写了那两行跳过逻辑首先它不会影响正确性。其次在特定测试用例上它有剪枝作用如果数组里大量重复元素固定同一个值反复跑内层 while 是浪费的因为固定的nums[i]相同、后面的双指针搜索范围又一样得到的候选和集合完全相同没必要重复算。但是要注意这里跳过的只是外层固定的i不是left和right。内层指针我们不去重因为我们需要把区间完整扫一遍去重反而可能漏掉两个重复值加另一个唯一值这种组合。很多从15题迁移过来的同学在left/right上去重结果在某些测试用例上答案错误这是这题一个很典型的坑。所以记住这句话这道题里外层i去重是优化内层不去重是正确性保证。4.3 C/Java 的溢出问题与 Python 的偷懒Python 选手在这题上确实可以偷懒——整数是任意精度的三个 int 相加不存在溢出。但如果你在面试里用 C 或 Java 写n 的范围稍大时nums[i] nums[left] nums[right]可能超出 int 范围虽然力扣原题的数据一般不会卡这个但面试官可能会主动问。稳妥的做法是把s定义成long long或long比较差值的时候也统一用long。Java 里可以写成long s (long) nums[i] nums[left] nums[right];先转long再加顺序很重要别写成long s (long)(nums[i] nums[left] nums[right]);——后者在括号里就已经溢出成 int 了转long也没用。这个细节是典型的看起来是小问题真爆了就是 WA。我在给团队 code review 时特意强调过遇到可能溢出的求和永远先转类型再运算而不是先运算再转类型。4.4 排序会原地修改数组一个容易被忽略的副作用最后一个容易被忽略的坑nums.sort()是原地排序。在力扣的评测环境里你只关心返回值数组本身被改掉没有关系。但如果你把这段逻辑嵌到更大的业务代码里nums是外部传入的引用排序之后外部看到的就是一个被打乱顺序的数组可能会引发一系列问题。如果你需要保留原来的顺序就改成nums_sorted sorted(nums)然后后面所有地方都用nums_sorted。虽然多一次拷贝但安全性提升很多。这也是我在实际项目里更推荐的做法算法题可以随便原地改工程代码对入参要怀有敬畏之心。5. 举一反三力扣排序双指针题型的识别与迁移5.1 同族题目一览一路打过去把这道题吃透之后可以顺手把整个排序双指针家族扫一遍。我按依赖顺序列了个清单这也是我自己刷题时验证过的顺序题目一句话思路与本题的关联两数之和 II - 输入有序数组(167)双指针收尾和为 target 时返回最简版只有一层双指针三数之和(15)固定 i 双指针需去重同一框架但要去重最接近的三数之和(16)固定 i 双指针维护最近差值本题四数之和(18)固定 i、j 双指针多套一层循环而已盛最多水的容器(11)双指针从两端向中间根据高度决定移动哪边贪心方向由高度决定有效三角形的个数(611)排序后固定最长边双指针数组合反过来用三数关系每个题我都建议在裸写代码之前先自己说一遍为什么这个方向移动是安全的能说出来说明你掌握了这套方法的思维内核。5.2 什么时候不能套这套路识别反例特征学会用这套手法的同时也要知道它的局限。第一个反例特征目标函数不满足单调性或者数组排序后会破坏问题约束。比如保持原数组相对顺序的题目排序会直接改变顺序双指针就不适用。又比如要找方差最接近的三数之和这类非线性的目标函数排序后单调性不成立双指针的贪心论证彻底失效。第二个反例特征数组元素可以重复使用。这种题往往不能用排序双指针直接套因为它等价于带放回的组合问题需要考虑元素复用对候选集的影响常见解法是回溯或动态规划。第三个反例特征数据规模极小比如 n 10这时候 O(n³) 暴力反而写起来最快最不容易错。不要为了炫技而用更复杂的解法工程上简单优于聪明。识别这些特征的能力需要靠一定量的题来养。我的经验是拿到一个和、最接近、最大最小、是否存在这类关键词的题先问自己三个问题——能不能排序固定一个变量后剩余问题是否单调双指针移动方向是否可以用排除法论证三个都满足就大胆上排序双指针。5.3 在热题100里的定位与刷题顺序建议最后把这题放回力扣热题100的坐标里看。热题100是很多人的复健清单第15、16、18这三道三数题目是连号出现的它们正好是一组由浅入深的梯度15题训练去重和双指针16题训练差值维护和贪心方向18题训练循环嵌套的层次感。我的建议是把这三题放在同一个晚上刷完先写15题再写16题最后尝试18题。刷16题的时候别急着看题解先自己在15题代码的基础上改一版感受一下只是把相等改成最接近这句话背后其实隐藏了多少细节。等你能不看任何笔记把这道题的关键论证讲清楚热题100里大部分数组类中等题你都有思路可循了。我自己后来刷接雨水、合并区间这些题时反复受益于这道题打下的底子——所谓刷题能力靠的从来不是背下一百道题的答案而是吃透几十道题背后的那几十种思维模型。