LeetCode Hot 100 里的双指针专题我前后刷了两遍每一遍都有新的理解。第一次是把题解背下来第二次才彻底想明白为什么两个指针来回移动几下就能把一个 O(n^2) 的暴力解法变成 O(n)如果你正在准备算法面试或者已经把链表、二分这些基础题过了一遍想系统整理哪几类题能归到“双指针”这篇应该能帮上忙。我会用 C 写题解代码里也顺带标注一些在 C 里特别容易踩的坑。这一专题几乎每次面试都会被问到核心题型不算多但覆盖了数组、字符串、链表三类场景。整理清楚之后你会发现在 Hot 100 里除了“滑动窗口”还有大概十道题本质上都在反复用同一套指针移动逻辑只是穿上了不同的外衣。下面我就按“思路 - 模板 - 经典题 - 进阶 - 排错”的顺序讲。1. 双指针到底在解决什么问题1.1 从两数之和 II 看双指针为什么比暴力快直接拿“两数之和 II - 输入有序数组”说事。题目要求在一个下标从 1 开始的有序数组里找两个数使它们的和等于 target。最土的做法是两层循环枚举所有数对遇到和等于 target 就返回复杂度 O(n^2)。但数组是有序的这一条信息没有被利用。双指针的做法很直白left 指向数组开头right 指向数组结尾。计算 sum numbers[left] numbers[right]sum target直接返回sum target说明左边的数太小了只能把 left 往右移sum target说明右边的数太大了只能把 right 往左移。为什么这种移动方式不会漏掉正确答案假设正确答案是 numbers[i] 和 numbers[j]且 i j。当 left 还没走到 i 时不管 right 在哪如果当前的 right 在 j 的右边sum 一定大于 target于是 right 会一直向左收如果 left 已经越过了 i那从 i 这个位置出发的答案早已被考虑过了。换句话说每一次移动都排除了一个“不可能再有解”的区间。这个思想贯穿所有左右指针题。从复杂度上看left 和 right 总共只会移动 n 次所以是 O(n)。这就是双指针最迷人的地方用有序性换掉一层枚举循环。1.2 三个判断条件哪些题目能用双指针后来刷多了我总结出三个判断条件基本能筛掉九成题。第一问题能否建模成两个元素之间的关系。找两数之和、三数之和、盛水容器里的面积都是两个位置共同决定结果。如果题目的答案要同时依赖数组里两个位置双指针就有戏。第二指针的移动方向是否单调。这里“单调”不是指数组本身单调而是指当某个指针移动到某个位置后如果当前组合不满足条件那向某个方向移动不会再带来更优解。比如三数之和里固定第一个数后sum 小于 0 就必须增大 left因为 left 再往左是不可能的while(left right) 这个结构保证了收敛。第三无序的输入能不能先排序。第一道两数之和不允许排序因为要返回原数组下标所以不能用双指针但第二道题输入已经有序排序也没有破坏返回下标的约束于是就能用。三数之和、盛水容器都能排序因为它们输出的是数值本身而不是下标。这个条件经常被忽略我见过不少人把需要返回原下标的题直接排序然后整个结果全错。满足这三个条件的题很大概率可以用双指针把复杂度往下压一档。不满足的通常也就别硬套了。2. C 的两种双指针模板与实现细节2.1 左右指针模板从两端向中间逼近的写法与坑左右指针的代码其实出奇地短int left 0, right (int)nums.size() - 1; while (left right) { if (check(left, right)) { // 记录答案具体看题目 } if (nums[left] nums[right] target) { left; } else { --right; } }这里有一个很多人一开始会写错的点循环条件是 left right不是 left right。因为双指针题里两个指针代表的是两个不同的位置相遇之后区间宽度为 0已经不存在有效的数对了。如果你写成 在个别题目里会把自己搞进死循环尤其是那种“记录完答案还要继续移动指针”的题。另一个细节是“记录答案”和“移动指针”的顺序。像两数之和这种题找到答案直接 return顺序无所谓但像三数之和这种题找到答案后要先把所有相同的数跳过再同时收缩两个指针否则会重复输出同一个三元组。我的习惯是先判断当前组合是否已经是答案再决定下一步怎么走不要反过来。2.2 快慢指针模板一个探路一个收尾的原地操作快慢指针专门处理一类“原地操作”的题目。比如把一个数组里的零全部移到末尾同时保持非零元素的相对顺序。很多人的第一反应是开一个新数组但题目要求原地。模板长这样int slow 0; for (int fast 0; fast (int)nums.size(); fast) { if (nums[fast] ! 0) { swap(nums[slow], nums[fast]); slow; } }理解快慢指针的关键是fast 负责探索整个数组每遇到一个符合条件的元素就把它放到 slow 指向的位置然后 slow 前进。slow 左边的区间永远是已经处理好的部分。这个“维护有效前缀”的视角比把代码背下来重要得多。很多变体题比如删除排序数组中的重复项把判断条件换成 nums[fast] ! nums[slow - 1] 即可核心思想完全一样。快慢指针和左右指针最大的区别在哪左右指针面对的是“从两边向中间收敛”的问题快慢指针面对的是“一个扫全图、一个收结果”的问题。前者通常利用有序性后者通常利用元素种类的可分性。拿到题先想清楚是哪一类再套模板思路会顺很多。2.3 C 双指针的三个易错点类型、边界、引用C 写双指针有几个坑几乎每场笔试都能见到。第一个是无符号整数。nums.size() 返回的是 size_t如果你直接写 int right nums.size() - 1当 nums 为空时 right 会变成 4294967295 这样的巨大正数while 循环直接崩。要么先判空要么先把 size 强转成 int。我现在一律写 int n (int)nums.size()省心。第二个是整数溢出。虽然 LeetCode 的测试用例大部分不会让 int 溢出但“两数之和”这类题里两个 int 相加最大值可能逼近 2^31稳妥起见我会在相加前先把值转成 long long。三数之和里三个数相加亦然。这个习惯不亏。第三个是排序丢下标。前面已经提过凡是题目要求返回原数组下标的情况排序前必须先把下标和值一起打包进 struct或者存到 map 里。这里不再展开。3. 三道最经典 Hot 100 题拆解3.1 三数之和去重关键排序固定一数双指针三数之和是双指针专题里最重要的一道题没有之一。题目要求找出数组中所有和为 0 的三元组且不能重复。整体的思路有三个步骤先排序再固定第一个数最后用双指针在剩余区间里找两数之和。固定第一个数为什么要排序因为排序后才可能用左右指针。如果不排序双指针无法保证单调性。完整代码vectorvectorint threeSum(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint res; int n (int)nums.size(); for (int i 0; i n; i) { if (i 0 nums[i] nums[i - 1]) continue; int left i 1, right n - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { res.push_back({nums[i], nums[left], nums[right]}); while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) --right; left; --right; } else if (sum 0) { left; } else { --right; } } } return res; }这里最容易被绕晕的就是去重逻辑。外层循环里的 if (i 0 nums[i] nums[i - 1]) 是防止同一个第一个数被重复使用内层找到一组答案后要先把 left 和 right 指向的下一个数字都跳过重复再同时收缩否则同一组三元组会被多次记录。注意有一个非常常见的错误是把外层去重写成 nums[i] nums[i 1]。这两个看起来差不多实际效果完全不同。写成 i1 会跳过“当前这个数作为第一个数”的所有情况直接导致漏解。比如 [-1, -1, 2] 这个三元组如果第一个 -1 因为和第二个 -1 相同被跳过就永远找不到答案了。正确写法是跟前一个比较而不是跟后一个比较。3.2 盛最多水的容器为什么每次都要移动矮的那边这道题输入是一个数组每个元素代表墙的高度要找两根柱子之间能盛的最大水量。公式是area (right - left) * min(height[left], height[right])暴力枚举所有柱子对能过但很慢。双指针的优化从两端开始每次都移动高度较小的一边。为什么因为面积由两个因素决定宽度和两侧较低的墙。如果把较高的那一边向内移动宽度在缩减而 min 的高度只会变得更小或不变面积不可能增大如果把较矮的那一边向内移动min 的高度有可能变大面积才有机会变大。这个逻辑其实就是贪心的思想每一步都主动放弃“不可能成为最优解”的区间。代码非常短int maxArea(vectorint height) { int left 0, right (int)height.size() - 1; int res 0; while (left right) { int area min(height[left], height[right]) * (right - left); res max(res, area); if (height[left] height[right]) { left; } else { --right; } } return res; }有同学会问如果 height[left] height[right] 时移动哪边代码里走了 else 分支也就是移动 right。其实两边都一样因为无论如何下一步都会重新计算这个相等的情况不会影响最终答案。实测下来移动哪边都不会漏解。这道题我还建议用一种“反证法”的方式来验证假设最优解在某个区间 (i, j)如果当前 left 还不到 i而 right 已经超过了 j那必然有一次移动会让指针离开最优区间那次移动一定是移走了较矮的一侧因为较高的一侧移走了会和“最优解”矛盾。想通这一点贪心的正确性就基本握住了。3.3 移动零快慢指针原地交换的最小实现移动零题目本身很简单把数组里所有 0 移到末尾非零元素保持相对顺序。但它是快慢指针思想的最佳入门题。双指针写法void moveZeroes(vectorint nums) { int slow 0; for (int fast 0; fast (int)nums.size(); fast) { if (nums[fast] ! 0) { swap(nums[slow], nums[fast]); slow; } } }模拟一遍就明白了fast 每遇到一个非零元素就把它和 slow 位置的元素交换。如果 slow 位置本身就是非零的那交换的两个位置相同结果不变如果 slow 指向的是已经排好的首部区域fast 则指向后面一个非零元素交换后这个非零元素被搬到了前面slow 再前移。这个过程里 slow 始终指向“下一个非零元素应该放的位置”而 fast 负责扫整个数组。等 fast 走到头所有非零元素都在 slow 左边剩下的位置自然全是 0。这么做的时间复杂度是 O(n)空间 O(1)满足很多面试官的额外追问。要注意的一个小坑如果数组长度为 1或者数组全是 0fast 每次都不满足条件slow 一直停在 0不会越界所以没问题。掉以轻心反而会在“给空数组”的测试用例上翻车。4. 从双指针到进阶用法4.1 接雨水双指针如何把动态规划压缩到 O(1) 空间接雨水在 Hot 100 里的位置很特别它既可以用动态规划也可以用双指针。如果你先做动态规划版本再理解双指针会对“指针移动为什么有效”有更深的感觉。动态规划的思路是对于每个位置 i它能接到多少水取决于它左边最高的柱子和右边最高的柱子中较矮的那个。如果这个“较矮的高墙”高于 height[i]就能接到高度差的水。所以要开两个数组 leftMax 和 rightMax 分别预处理。双指针的做法把空间压缩到 O(1)核心逻辑变成了当 height[left] height[right] 时处理 left 位置否则处理 right 位置。为什么能这么做关键在“结算较矮的一侧”。以处理 left 为例leftMax 已经记录了 left 左侧扫过的最高的墙而右侧当前边界 height[right] 比 left 位置的柱子高。由于 left 能移动到当前位置说明右侧的墙比 left 左侧遇到过的所有柱子都高因此右侧最终的峰值一定不会低过 leftMax。所以 left 位置能接多少水就完全由 leftMax 决定。代码int trap(vectorint height) { int left 0, right (int)height.size() - 1; int leftMax 0, rightMax 0; int ans 0; while (left right) { if (height[left] height[right]) { if (height[left] leftMax) { leftMax height[left]; } else { ans leftMax - height[left]; } left; } else { if (height[right] rightMax) { rightMax height[right]; } else { ans rightMax - height[right]; } --right; } } return ans; }考试时如果一时没想起来双指针版本动态规划版本也能过关。双指针版本的魅力在于把两个预处理数组变成了两个滚动变量思路更逼近“左右高墙的临界点”。4.2 颜色分类三指针解决荷兰国旗问题颜色分类题要求原地把数组排成 0、1、2 的顺序只有三个值。它被归到双指针专题严格来说是双指针的升级版三指针。思路是维护三个区域p0 指向下一个 0 应该放的位置p2 指向下一个 2 应该放的位置cur 从头扫到尾。cur 遇到 0就和 p0 交换p0 和 cur 都前进遇到 2就和 p2 交换p2 后退但 cur 不前进遇到 1cur 直接前进。为什么遇到 2 时 cur 不能前进因为从 p2 换过来的数可能是 1也可能是 0还没有被归类过必须原地再检查一次。这个细节是荷兰国旗问题的灵魂也是最容易写错的地方。完整代码void sortColors(vectorint nums) { int p0 0, p2 (int)nums.size() - 1; int cur 0; while (cur p2) { if (nums[cur] 0) { swap(nums[p0], nums[cur]); p0; cur; } else if (nums[cur] 2) { swap(nums[p2], nums[cur]); --p2; } else { cur; } } }你可以把这道题理解成“两个左右指针 一个扫描指针”的配合。它告诉我们双指针的框架并不死板根据需要可以扩展成三个指针核心依然是指针所划定的边界。4.3 最长回文子串中心向外扩展的双指针变体最长回文子串是字符串题里的一道经典虽然分类往往不在双指针专题里但它内部用的就是双指针的思想只不过方向相反不是从两端向中间夹而是从中心向两边扩。实现思路枚举每个位置作为中心点奇数长度回文中心是一个字符偶数长度回文中心是两个相邻字符。对每一种中心用两个指针向左、向右同时扩展直到字符不同或越界。string longestPalindrome(string s) { int n (int)s.size(); if (n 2) return s; int start 0, maxLen 1; for (int i 0; i n; i) { auto expand [](int l, int r) - int { while (l 0 r n s[l] s[r]) { --l; r; } return r - l - 1; }; int len1 expand(i, i); int len2 expand(i, i 1); int len max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } } return s.substr(start, maxLen); }这里 expand 函数里的 while 循环本质就是两个指针分别往两侧探路。掌握了“指针移动的方向不是固定的既可以相向也可以相背”这一点字符串类的很多题也会豁然开朗。5. 踩坑实录常见错误与排查方法5.1 死循环和漏解的两种典型场景我刷题时遇到最多的死循环基本都出在“记录答案后忘记移动指针”和“移动指针的幅度小于应有的幅度”两种场景。第一种典型是三数之和里找到一组答案后只把 left 或 right 其中一个移动一个单位另一个没动。比如 sum 0 后只写了 left没有写 --right那 left 到下一个位置后right 还是原来的位置如果 nums[left1] 和 nums[left] 相等就还会再匹配出同一组三元组甚至陷入无限循环。解决方式前面已经写了两个指针都跳过重复并收缩。第二种典型是快慢指针里 slow 只在满足条件时移动但 fast 的移动循环被误写成 while 而不是 for。比如移动零里如果用 while 代替 for忘记在每次循环末尾给 fast 加一一定会卡死。我的建议是写完代码先自己走一遍两到三行的样例慢慢挪动指针确认每一步都必然前进。漏解的场景集中在去重逻辑写反。三数之和外层去重写成 nums[i] nums[i1] 会漏解前面已经说过了。还有个容易漏的是内层去重后忘记再 left / --right 一下导致一轮循环结束后指针没有越过重复区间下一轮匹配的还是同一批重复值。5.2 边界条件和整数溢出的排查细节边界条件核心就是三个词空、单个、相等。空数组或空字符串很多双指针版本会直接访问 nums[0]必须先判空单个元素比如移动零里数组只有一个 0slow 始终为 0没问题但如果你在 while 循环里写了 right - 1 之类的操作就要小心相等元素比如盛水容器里 height[left] height[right] 时无论移动哪一边都不会错但有些变体题遇到相等时移动策略不同会得出不同结果需要先仔细读题。整数溢出这块C 的 int 范围是大约正负 2.1e9如果题目的数值范围比较大比如两数之和的数组成员可以到 10^9两个相加就到 2e9还在 int 范围内但三数之和呢三个 10^9 就是 3e9已经爆了。LeetCode 题目通常不会把这些极端情况全放在小数据里测但面试官扩展时喜欢追问。稳妥做法是统一用 long long 参与计算或者在相加前先做一次类型转换。5.3 常见错误速查表几道高频题的坑我把平时遇到的、以及在群聊里看大家问得最多的问题整理成了一张表症状原因解决方法三数之和输出重复三元组外层去重写成 nums[i] nums[i1]改成 nums[i] nums[i-1]三数之和死循环找到答案后没跳过重复区间内层加 while 跳过再双指针同时收缩移动零结果顺序错乱slow 维护的边界不清记住 slow 指向下一个应放置元素的位置双指针题数组越界nums.size() 返回无符号类型先转 int先判空接雨水结果偏小左右最大值的更新写在了累计之后一定要先更新最大值再计算水量排序后答案全错题目要求返回原数组下标排序前打包下标或使用 map 映射颜色分类结果混乱cur 遇到 2 交换后仍向前交换后 cur 不前进再检查一次这张表还可以继续补充但核心规律就是双指针的题大部分错误都能归结为“指针移动的时机不对”或“边界维护的范围不清”。debug 的时候顺着这两条线去查一般都能很快定位。我个人刷下来还有一个习惯每道双指针题做完了都会在草稿纸上画一下指针移动的完整路线然后问自己一个问题——刚才那步移动为什么不会漏掉最优解如果答不上来说明这道题还没真正搞懂。这个习惯帮我避开了大量“背题解”式的无效刷题。建议你也试试。最后再分享一个小技巧把双指针和滑动窗口放在一起对比学习。左右指针是两端夹逼快慢指针是单向推进滑动窗口是同向双指针的进阶三者本质上都是“用两个边界来维护一个区间”。透彻理解其中一种另外两种的代码理解起来会快很多。
