今天要聊的是三道人气极高的 LeetCode 原题11. 盛水最多的容器、15. 三数之和、283. 移动零。如果你正在按“LeetCode 热门 100 题”刷面试题大概率会先后撞见它们。我自己的感觉是单独刷每一题都能看懂题解但真要合在一起体会才会发现这三道题就像一套“双指针组合拳”一个练收缩边界一个练排序后双指针加去重一个练快慢指针原地操作。这篇就按我日常刷题的实际顺序展开顺便把我在代码里踩过的坑都摊开来说。先说适合谁读准备校招、社招算法面试的人尤其是双指针掌握得还不够稳的刚入坑 LeetCode 想找一份能“照着做”的解题笔记的新手以及刷过一遍但容易在边界条件上栽跟头的老手。三道题的难度分别是中等、中等、简单但简单题不一定容易写对中等题里也有很多细节值得扣。接下来我不讲虚的直接说题。1. 三道题放在一起刷比单刷更有价值很多人刷题习惯按题号顺序来今天 11明天 15后天 283结果刷完就忘。我个人强烈建议把这一类题按“招式”归类。11、15、283 表面上看毫不相干一个求最大面积一个求三元组和为零一个是把零移到末尾。但它们骨子里都在考同一件事如何在一个数组上用指针把暴力枚举的复杂度降下来。先说 11 题它是最纯粹的“双指针收缩”模型。左右两个指针夹出一个区间每次根据瓶颈缩小一侧直到碰头。这个模型是所有双指针思想的基础也是后面很多 hard 题的雏形比如接雨水、最大矩形。15 题则是在“双指针”前面加了一步排序。排序让无序数组拥有了单调性于是两数之和能用双指针在线性时间内解决再套一层外层循环整体就是 O(n^2)。它比 11 题更难的地方在于“去重”。很多新手写出代码后输出的三元组里有重复项或者反过来漏掉包含重复元素的有效解问题大多出在去重条件的写法上。283 题更基础但也最容易大意。它要求原地移动零意思是空间复杂度不能是 O(n)不能开一个新数组再拷回来。主要用到的是快慢指针慢指针维护“非零元素的下一个写入位置”快指针负责扫描。看起来简单但不少人会因为“覆盖后忘了清零”“交换顺序写反”这种低级错误浪费一次提交机会。所以我的建议是不要把这当三道孤立的题而是用一天的时间把“双指针”这个专题打通。上午做 11 和 283下午做 15再配合几道同类变体比如“最接近的三数之和”“四数之和”“颜色分类”。这样刷下来的效果比随机刷 30 道题都强。2. 盛水最多的容器双指针的第一次觉醒2.1 先想暴力枚举别上来就背模板11 题的题意其实非常直白给定 n 个非负整数 height每个数代表坐标点 (i, height[i]) 上的一条垂线。要找两条线和 x 轴一起围成一个容器问容器最多能装多少水。容器的面积公式是面积 (右边界下标 - 左边界下标) × min(height[左], height[右])为什么高度取 min因为水装到矮的那条边就会溢出这是容器盛水的基本常识。很多新手第一反应是暴力枚举所有下标对也就是双重循环时间复杂度 O(n^2)。这个思路本身没错面试时先说出来还能证明你理解题目。但 n 的范围通常是 10^5 甚至更大O(n^2) 根本过不了。于是核心问题变成了怎么把枚举 i j 的 n^2 个组合压缩到 O(n)我当年学双指针时最大的误区就是想直接记住“左右指针移动”的结论却不理解为什么这样移动不会漏掉最优解。这种理解程度一旦遇到变体题就会露馅。所以下面我把推导过程完整写一遍。2.2 为什么移动较矮的一侧才是正确答案假设当前左指针 left 指向 height[left]右指针 right 指向 height[right]当前宽度是 right - left。面积 (right - left) × min(height[left], height[right])现在分两种情况。第一种情况height[left] height[right]也就是左边更矮。此时容器的高度被左边界卡住高度是 height[left]。如果我把右指针向左移动一步新的高度一定小于等于 height[left]宽度也一定更小所以新的面积一定比当前面积小。换句话说右指针往左走一步等于用一个更矮或一样高的木板换掉了原本较高的木板同时还缩窄了宽度不可能得到更大的面积。那么以当前 right 为右边界的组合还有没有可能产生更大面积没有。因为右边界已经足够高但宽度限制了它再怎么移动右边都没用。所以这一轮结束之后左指针 left 可以安全地向右移动一位因为以它为左边界的最大面积已经被探索完了。第二种情况完全对称height[left] height[right] 时应该移动右指针。如果 height[left] height[right]移动哪边都可以。当前左右边界都是瓶颈无论移动哪一边宽度都会变小高度也不会变高面积不可能再增大。实现里随便选一边移动不影响最终结果。这个推理是 11 题的核心。每一步都移动“较矮”的那一侧本质上是在排除不可能产生最优解的区间端点。双指针之所以能保证找到全局最优解不是因为每一步都贪心选择了当前最好的下一步而是因为每一步都理性放弃了一大片不可能的区域。2.3 代码实现和最容易犯的错我在 LeetCode 上提交的 Python 版本长这样def maxArea(height): left, right 0, len(height) - 1 ans 0 while left right: area (right - left) * min(height[left], height[right]) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ans复杂度是 O(n) 时间O(1) 空间。这里有一个我见过很多人踩的坑把min(height[left], height[right])写成max。如果用了max语义就变成了“水能超过短板继续装”那显然是错的而且部分测试用例还可能会给出一个看起来合理的结果导致你很难定位问题。另一个细节是 while 条件的边界。while left right保证至少有两个位置参与计算写成while left right也能跑但当 left 和 right 重合时左右边界相同面积是 0毫无意义所以没必要。面试时如果把等号带上反而可能被追问边界逻辑。还有一个容易忽略的点如果数组长度小于 2根本不存在容器应该直接返回 0。LeetCode 的测试用例一般不会让你在这个问题上翻车但自己写工具函数时建议加上if len(height) 2: return 0最后补充一个面试常问的延伸11 题的姐妹题是“接雨水”但两者的思路差别很大。盛水是找两条边界围成的最大矩形接雨水是计算每个凹槽能接住多少水。很多人把这两个模型记混面试时被问“你能不能用 11 题的双指针方法解决接雨水”如果你能说出它们的区别会是很加分的回答。3. 三数之和排序、双指针、去重的三重奏3.1 排序是双指针能用的前提15 题的要求是给一个整数数组 nums返回所有和为 0 且不重复的三元组。注意“不重复”三个字是这道题的一半难点。最暴力的办法是三重循环枚举每个组合然后用哈希表去重时间复杂度 O(n^3)空间开销也不小。这显然不行。常规做法是先把数组排序。排序以后数组有了单调性原本“无序数组中找两数之和”的问题变成了“有序数组中找两数之和”后者可以用双指针在线性时间内完成。具体思路是外层循环固定第一个数 nums[i]然后在剩下的区间 [i1, len(nums)-1] 里用左右指针找两个数让它们的和等于 -nums[i]。因为数组已经排序当双指针指向的数字之和小于目标时左指针右移大于目标时右指针左移。这样每次固定一个 i内层双指针是 O(n)总复杂度是 O(n^2)。这里有一个很关键的理解为什么排序不会破坏答案因为三元组是由数组里元素的值决定的不是由下标决定的。排序之后数组元素会重新排列但每个三元组的值仍然存在只是顺序变了。题目要求返回的是值不是下标所以排序可以放心用。3.2 去重逻辑是这道题的灵魂去重是 15 题最容易写错的地方。我见过两个非常典型的错误版本。第一个错误外层循环里写if nums[i] nums[i 1]: continue。这个写法看着像是“跳过重复元素”但方向反了。它跳过的不是“当前已经处理过的相同值”而是“下一轮的相同值”。举个例子数组[-1, -1, 2]正确答案是[-1, -1, 2]这需要一个负数 -1 和一个正数 2。如果 i 从 0 开始判断nums[0] nums[1]成立于是 continue直接把 i0 这个位置跳过了后面等于 2 的补数就找不到了结果漏解。正确的写法是和“上一个已经处理过的”值比较也就是if i 0 and nums[i] nums[i - 1]: continue。原因在于当 i 往前扫描时如果 nums[i] 和 nums[i-1] 相等说明这个固定值已经被处理过了它所能产生的所有双指针组合都已经探索过没有必要再重复。如果不加这个判断结果里会出现大量重复三元组。第二个错误找到一组解之后没有做内层去重。很多人写成这样if left_sum right_sum target: res.append([nums[i], nums[left], nums[right]]) left 1 right - 1看上去逻辑没错但紧接着就可能把相同值造成的重复组合再次加入答案。比如[-2, 0, 0, 2, 2]固定 i0 时目标等于 2left1 是 0right4 是 2找到一个解[-2, 0, 2]。此时如果只做 left 1、right - 1left 仍然指到 0right 指到 2又会找到同一个三元组。所以找到解以后必须额外用两个 while 循环跳过所有与当前值相同的元素while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1这段逻辑的意图是既然 left 位置的数字已经被用于凑出一组解那么所有和它相等的数字都不可能再产生新的不同三元组全部跳过。right 同理。完整代码我贴在下面你可以直接对照着调试def threeSum(nums): nums.sort() n len(nums) res [] for i in range(n - 2): if nums[i] 0: break if i 0 and nums[i] nums[i - 1]: continue target -nums[i] left, right i 1, n - 1 while left right: s nums[left] nums[right] if s target: left 1 elif s target: right - 1 else: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 return res这里我加了一个小优化排序后如果 nums[i] 0直接结束循环。因为后面的数都大于 0三个正数不可能相加等于 0。同理如果 nums[i] nums[i1] nums[i2] 0 也可以提前结束但那个判断不是必须的面试时提不提都行。复杂度排序 O(n log n)主循环 O(n^2)空间复杂度 O(1)不计返回值占用的空间。严格来说官方认为排序可能占用 O(log n) 到 O(n) 空间取决于排序实现但一般面试分析里都说 O(1)。3.3 变体题怎么迁移三数之和这道题可以轻松迁移到好几个常见变体最接近的三数之和要求找到和最接近 target 的一个三元组并返回其和。不同点是每次计算 diff不断更新答案并且不需要去重因为只求一个值。四数之和多加一层循环固定两个数然后仍然用双指针复杂度变成 O(n^3)。三数之和小于 target 的个数这类题会要求不重复地计数可以在双指针时计算区间长度来批量统计。如果你能理解 15 题为什么这样去重这些变体题完全不需要背现场都能推出来。4. 移动零原地操作里的低调高手4.1 快慢指针到底在维护什么283 题的要求是把数组里的所有 0 移动到末尾同时保持非零元素的相对顺序并且必须原地操作不能复制数组。题目非常简单但很多人第一次写的时候会写出“复制一个新数组”的版本那就违背题意了。先想清楚约束空间复杂度 O(1)说明只能在原数组上挪动元素。最优雅的做法是快慢指针也叫覆盖法或者交换法。这里我以交换法为例因为它最符合“原地”这个要求。先定义两个指针slow 指针下一个非零元素应该放的位置fast 指针当前扫描到的位置。循环不变量可以表达为区间[0, slow)内全是非零元素区间[slow, fast)内全是 0区间[fast, n-1]是尚未扫描的部分。当 fast 遇到非零元素时就把它和nums[slow]交换然后 slow 加一。为什么可以交换因为[slow, fast)里全是 0交换之后非零元素被挪到前面0 被挪到后面顺序不会乱。我用示例[0, 1, 0, 3, 12]一步步模拟。初始状态slow 0fast 0数组是[0, 1, 0, 3, 12]此时 nums[fast] 0跳过。fast 1nums[1] 1非零。交换 nums[0] 和 nums[1]数组变成[1, 0, 0, 3, 12]slow 变为 1。fast 2nums[2] 0跳过。fast 3nums[3] 3非零。交换 nums[1] 和 nums[3]数组变成[1, 3, 0, 0, 12]slow 变为 2。fast 4nums[4] 12非零。交换 nums[2] 和 nums[4]数组变成[1, 3, 12, 0, 0]slow 变为 3。扫描结束得到结果[1, 3, 12, 0, 0]。这个过程里非零元素依次前移而且相对顺序原封不动。你可能会问如果当前 fast 和 slow 指向同一个位置怎么办比如数组[1, 2, 3]第一个元素就是非零slow fast 0交换后数组不变。虽然多了一次“自己和自己交换”但代码逻辑仍然正确。如果你对这一点有洁癖可以在交换前加判断if fast ! slow但不是必须的。4.2 两套官方解法的取舍除了交换法LeetCode 官方题解其实更推荐“先覆盖所有非零元素再统一补零”的思路def moveZeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow] nums[fast] slow 1 for i in range(slow, len(nums)): nums[i] 0第一轮扫描把每个非零元素按顺序搬到数组前部第二轮扫描把后面剩余位置全部填 0。这个做法赋值次数稳定逻辑也更简单很多教学文章里都用它。那到底应该用哪种我的建议是面试时先写覆盖法因为它不容易出错然后再补充一句“其实也可以用交换法一次遍历完成”。如果你直接写交换法要能清楚地解释 slow 和 fast 之间为什么全是 0。两种写法都满足 O(n) 时间、O(1) 空间但覆盖法的代码稍长交换法更显技巧。实际刷题时LeetCode 的判题系统对这两种写法都友好。不过如果面试官追问“尽量减少操作次数”覆盖法在第一轮把非零元素复制到前面后忘了补零就会留下旧值交换法则天然不需要补零。这里提醒一下覆盖法必须记得补零很多人就是漏掉最后一个 for 循环导致结果完全错误。4.3 边界条件与“零”背后的延伸题边界条件很好测空数组、只有一个元素、全部是零、全部非零、零和非零交替出现。这些用例我都用过可以保证你快速定位问题。有一个细节值得注意如果数组里一个零都没有交换法的 slow 始终和 fast 同步数组不会被修改性能也很好覆盖法则会把每个非零元素原位置复制一遍最后再跳过补零循环。但两者的复杂度级别一样面试中不需要纠结。移动零这道题其实可以看成一个更大问题的退化版本荷兰国旗问题。荷兰国旗要求把数组分成小于、等于、大于三个区域移动零只分“非零”和“零”两类所以是二分类的简化版。下次你刷到 75. 颜色分类也就是荷兰国旗问题时你会发现它的三指针思想和这里的快慢指针一脉相承。面试中常见的追问是“如果题目要求把指定的 target 值全部移到末尾非 target 保持相对顺序怎么做”处理方法完全一样只是把判断条件从nums[fast] ! 0改成nums[fast] ! target。甚至很多场景要求移动负数、移动偶数原理都是通用的。5. 三道题实战中我遇到的坑和排查技巧5.1 高频错误速查表我把三道题里出现频率最高的错误整理成了表格方便你自查题目典型错误原因正确做法11 盛水容器面积计算时用max(height[left], height[right])把“容器能装多少”理解成了“更长的板”用min短板决定高度11 盛水容器移动较高的指针没有理解双指针收缩只会移动矮侧比较两个高度矮侧移动15 三数之和if nums[i] nums[i 1]: continue跳过了必须使用当前重复值的解改为和nums[i - 1]比较15 三数之和找到解后不跳过左右重复值产生重复三元组用 while 跳过重复值再移动指针283 移动零覆盖法忘了末尾补零非零元素挪走后旧位置残留原值第二轮 for 循环统一补零283 移动零用新数组保存结果违反了原地操作的空间要求用 slow/fast 双指针原地交换这张表是我带新人时最常用的一张表基本覆盖了这道题线上提交过程中 80% 的失败原因。5.2 排查思路从“看懂”到“写对”我发现很多读者卡在“看懂了题解但自己写不出来”的状态。解决的方法只有一个不要只顾着看代码用手在草稿纸上走一遍循环。比如三数之和别急着写代码先把[-1, 0, 1, 2, -1, -4]排序成[-4, -1, -1, 0, 1, 2]然后在草稿纸上按固定 i0、i1、i2 逐轮推导每一步都记录 left、right、当前和、是否去重。推完一遍之后你才会理解为什么去重条件要和前一个元素比较而不是和下一个元素比较。另外我建议把所有双指针题的循环不变量写出来。11 题的循环不变量是“当前区间内还剩有可能产生全局最优解的组合”15 题是“固定 i 后区间 [i1, n-1] 中 left 和 right 之间所有可能的组合还没有被完全探索”283 题是“slow 之前全非零slow 到 fast 之间全零fast 之后未处理”。你只要能用自己的话把不变量说清楚代码基本不会写错。一个非常实用的技巧是提交之前先用几个边界测试用例手算一遍。11 题测[1, 1]15 题测[0, 0, 0]283 题测[0, 0, 1]。这些都是容易暴露出逻辑漏洞的小样例跑一遍比盯着代码看十遍更管用。5.3 从这三道题里提炼出的通用方法论刷完这三题之后我发现它们像一个方法论的三级台阶。第一级是 11 题理解“为什么双指针不会漏解”。这是所有双指针问题的基础也是面试官最爱深挖的地方。你要能清晰地证明每次移动较矮一侧是在排除一个不可能产生最优解的区间端点。第二级是 15 题理解“双指针和排序的配合”。排序解决的是数组的无序性双指针利用的是有序性。遇到无序数组里的多指针问题优先想排序。同时这道题教会我们如何优雅地处理重复结果这种去重意识在做排列组合类题目时特别重要。第三级是 283 题理解“指针之间的区间语义”。慢指针和快指针中间到底是什么想清楚了代码就迎刃而解。很多中等题、难题比如合并两个有序数组、删除排序数组中的重复项核心都是同一套东西。我个人在实际操作中的一个体会是刷算法题不要追求“一次写对”而要追求“错了之后能快速定位”。LeetCode 的好处是它有非常清晰的测试用例如果你提交后发现某个用例挂了就把那个用例拿出来手动走一遍代码。多数情况下你会发现不是逻辑看不懂而是某个细节没照顾到比如去重方向写反了或者补零循环漏了。最后再分享一个小技巧如果你在准备面试建议把这三道题按“自己能推导”的标准来复习而不是“看过题解会写”的标准。面试官一旦追问“为什么你这里选择移动右指针”“为什么你这么去重不会漏掉答案”你如果只能答一句“模板就是这样”那大概率要减分。这三道题都足够经典值得你花一个下午的时间把每一步推理和实现细节都吃透。等真正把这三题讲明白你手里的双指针基础就非常扎实了后面再刷 hard 题会轻松很多。