双指针这个技巧在 LeetCode 题解里出现的频率基本上和大厂面试手撕算法的频率持平。说实话我刷题到现在有个很深的感触很多看似毫无关联的题最后落到解法上翻来覆去就是双指针的那么几种套路。这个系列前两篇聊了数组基础和一些入门暴力思路这篇专门把“双指针”单独拎出来写是因为它真的太容易被低估了。很多人一开始觉得双指针不就是两个下标吗有什么好学的。可真到了笔试或者周赛现场遇到“三数之和”“最长无重复子串”“链表倒数第K个节点”这些变种经常会出现两种情况一是知道该用双指针但边界处理不好二是压根判断不出来这题其实是双指针的套壳。这篇刷题记录我就把这几个月刷下来觉得最有代表性的双指针题目重新梳理一遍包括左右对撞、快慢指针、滑动窗口三类模型以及去重、判空、循环条件这些容易翻车的地方。不管你是刚开始刷 LeetCode 的简单题还是已经在冲 Hot 100、周赛这篇文章都值得花二十分钟过一遍。我尽量不堆结论直接把当时的思考过程、写错的版本和修正后的代码都贴出来这样你复现的时候能少踩几个坑。1. 双指针到底是什么一次看清三类核心模型1.1 为什么两个指针比一个指针快先从最朴素的问题说起一个数组让你找两个数相加等于 target你会怎么做最简单的暴力法是两层循环外层固定一个数内层再遍历剩下的所有数。时间复杂度 O(n^2)数据量一大就完蛋。双指针的思路是与其让内层指针从头到尾扫描不如利用数组本身的一些性质让两个指针从两端或者同向移动跳过那些明显不可能的区间。用一个生活化的例子想象你在一条排列整齐的货架前找两瓶酒价格从左到右从低到高。暴力法是每拿一瓶就把后面所有酒都拿起来看一遍双指针的做法是你左手从最便宜那头开始右手从最贵那头开始两瓶价格加起来太贵了就往左挪右手太便宜了就往右挪左手。每一步你都能排除一整段货架而不是只看一瓶。这里最关键的点在于“排除了不可能的区间”。双指针之所以能把 O(n^2) 降成 O(n)不是因为两个指针做了更复杂的事而是因为指针移动的那一刻你根据数据的有序性或者某种约束一次性砍掉了大量不需要比较的组合。1.2 三种模型分别是干什么的我刷了这几个月自己心里把双指针分成了三类左右对撞指针两个指针从数组两端出发往中间走通常处理有序数组、回文判断、容器面积、两数之和等问题。快慢指针两个指针从同一端出发速度不一样通常用来处理链表环、链表中点、链表倒数第K个节点、原地去重等问题。滑动窗口也是两个指针同向移动但是维护的是一个连续的区间通常处理子串、子数组的统计问题。这三类对应着不同的输入形态和题目特征。比如输入是链表大概率是快慢指针输入是有序数组优先想左右对撞输入要求找连续一段、统计字符次数基本就是滑动窗口。有一个很常见的误区是看到题目里有“连续”“子数组”就直接上滑动窗口这是不行的。滑动窗口需要窗口的右边界移动时能明确判断出“什么时候该收缩左边界”如果这个判断条件不存在那滑动窗口就是伪命题。后面我会专门讲这个判断怎么建立。1.3 反面教材不是所有题都能套双指针这里想提醒一句判断题型比背模板更重要。拿热词里出现的两道题举例LeetCode 994 腐烂的橘子。很多人一看矩阵、扩散、层数就以为是双指针或者滑动窗口。实际上这题是标准的 BFS广度优先搜索要用队列按层传播腐烂状态。如果硬套双指针连状态存储都会变成灾难。LeetCode 073 爱吃香蕉的狒狒。看似是遍历每一堆香蕉、计算吃的时间好像有个“移动指针”的过程但这题真正的解法是二分答案——通过猜总用时判断当前速度是否可行。这两道题被我拿出来说不是否定双指针而是想强调双指针是一种“结构性”的解法它依赖数据的排布方式。遇到一道新题先判断输入形态和约束再看是不是能套模型。顺序反了代码写得再漂亮也是事倍功半。2. 左右对撞指针先解决“两数之和”到“三数之和”的进化2.1 最基础模板有序数组的两数之和LeetCode 167 题是左右对撞最经典的入门题输入是已经按升序排列的数组让你找两个数使它们的和等于 target。这题不用哈希表一个双指针就能搞定def two_sum(numbers, target): left 0 right len(numbers) - 1 while left right: current_sum numbers[left] numbers[right] if current_sum target: return [left 1, right 1] elif current_sum target: left 1 else: right - 1 return []这里的移动逻辑值得展开说。当 current_sum 小于 target 时说明整体太小右指针已经指向数组最大值往左移动右指针只会让和更小所以唯一的希望是把左指针往右挪找一个更大的数。反过来也一样。每一步都能把搜索区间缩小一个单位所以整体是 O(n)。我一开始写的时候有个低级错误把循环条件写成了while left right。表面看没什么但如果是left right时两个指针指向同一个数会导致下标重复或者死循环。对撞指针的终止条件永远是left right除非题目允许同一个元素用两次但那种情况一般题目都会明确说。2.2 三数之和去重才是真正的考点LeetCode 15 题三数之和可以说是左右对撞里最经典也最容易犯错的一道。题目要求找出所有和为 0 的三元组并且不能重复。思路很好理解先排序然后固定一个数nums[i]在[i1, n-1]区间内用双指针找两个数使它们的和等于-nums[i]。这样就把时间复杂度控制在 O(n^2)。难点在于三个层面的去重外层固定的数不能重复。找到一组解后左指针要跳过重复的值。右指针也要跳过重复的值。我当时第一次写的时候只做了第一层去重结果提交后返回了很多重复三元组。后来仔细想才明白找到一组解之后如果你不跳过那两个位置的重复值下一轮可能又组出同样的三元组。以下是我修正后的版本def three_sum(nums): nums.sort() result [] n len(nums) for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue left i 1 right n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: result.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 elif total 0: left 1 else: right - 1 return result这里有个顺序问题值得强调先记录有效答案然后再跳过去重。如果顺序反了先跳过重复值再记录会漏掉正确结果。因为你是靠“当前这组值”判断是否等于 0 的跳过之后指针指向的值已经变了。2.3 从三数之和到四数之和套娃可以注意范围四数之和LeetCode 18其实就是三数之和外面再套一层循环先固定两个数再对剩下的区间做双指针。复杂度和去重逻辑完全同理只是代码上多一层continue判断。我在刷这题时发现一个规律这类“K 数之和”的题难度不在双指针本身而在于排序后有多少种“跳过重复”的组合。写之前先在纸上把所有去重位置标出来代码才不会乱。具体做法是外层每一层for循环都要判断当前值是否和上一个值相同相同就跳过。最内层双指针找到答案后左右都跳过重复值。如果当前的固定值已经让最小值大于 target 或者最大值小于 target可以直接剪枝能省不少时间。说句实话四数之和在面试中出现的频率不如三数之和但它是很好的练习能检验你是不是真的理解了嵌套循环里的指针关系而不是背下了某个题的解。2.4 面积和接水问题左右对撞的另一个分支除了求和类左右对撞还经常用来解决“形状”类问题最典型的就是 LeetCode 11 盛最多水的容器和 42 接雨水。盛最多水的容器这题两个指针分别指向容器左右边界面积等于短边高度乘以宽度。移动指针时总是移动较短的那一边因为容器的盛水量由短板决定移动长板只会让宽度减小而高度不可能变大面积必然不会增加。移动短板才有可能在“高度增长”和“宽度减少”的博弈中找到更大的面积。这个证明不复杂但很多人会凭直觉写错写成移动长板结果答案差很多。接雨水则稍微复杂一点需要维护左右两侧的最大高度。用双指针时每次比较left_max和right_max哪边小就计算哪边的水量然后移动对应指针。核心思想是当前位置能接多少水取决于较矮一侧的最大高度。这题容易和单调栈混淆其实两种都能做双指针的优势是空间 O(1)代码也更简洁。3. 快慢指针链表问题的大半江山3.1 快慢指针到底快在哪数组有下标链表没有。很多链表题天然适合用两个指针一个走两步一个走一步用速度差来制造“位置关系”。最经典的场景是判断链表有没有环。LeetCode 141 环形链表快指针每次走两步慢指针每次走一步如果链表有环两个指针最终一定会在环内相遇。这个结论的直觉是进入环之后快指针每次比慢指针多走一步相当于在环形跑道上不断追赶只要跑得足够久必然套圈追上。如果链表没有环快指针会先到达链表尾部遇到None就结束。所以在循环条件里要同时判断fast和fast.next是否为 Nonedef has_cycle(head): if not head or not head.next: return False slow head fast head.next while slow ! fast: if not fast or not fast.next: return False slow slow.next fast fast.next.next return True这里我把快指针初始化成了head.next而不是head。两套写法差别不大但初始化成head.next可以避免一上来就slow fast导致误判成有环。这个细节网上很多题解提了一嘴但不注意的话会让你 debug 很久。3.2 链表中点与回文链表和环形链表紧密相关的是找链表中点。快指针每次走两步慢指针每次走一步当快指针到尾部时慢指针正好在中点。LeetCode 876 链表的中间节点直接套用这个模板。这里需要注意的是偶数长度和奇数长度的差异链表有 6 个节点时慢指针会指向第 4 个节点靠右的中点有 5 个节点时指向第 3 个节点。如果你想取靠左的中点需要调整初始化方式。回文链表LeetCode 234就是把“找中点”和“反转链表”结合起来的经典题。先用快慢指针找到中点再把后半段反转然后前半段和后半段逐一比较。这题的考点不是双指针本身而是双指针和其他技巧的配合。我第一遍刷的时候直接用了列表存所有节点值虽然能过但面试时面试官大概率会追问“能否用 O(1) 空间”所以快慢指针版本才是更值得练的解法。3.3 删除链表倒数第 N 个节点一前一后指针的实战除了快慢速度差还有一种“间隔固定距离”的双指针用法专门处理“倒数第 K 个”这类问题。LeetCode 19 删除链表的倒数第 N 个节点。思路是让第一个指针先走 N 步然后第二个指针从头部出发两个指针保持 N 的距离一起走。当第一个指针走到链表末尾时第二个指针正好指向倒数第 N 个节点的前一个节点直接在它后面做删除操作。这里有个非常重要的细节是使用 dummy node哑节点。如果不用 dummy当链表长度等于 N 时要删的就是头节点逻辑上要多一个分支判断。用了 dummy 之后所有情况统一处理代码干净很多def remove_nth_from_end(head, n): dummy ListNode(0, head) first head second dummy for _ in range(n): first first.next while first: first first.next second second.next second.next second.next.next return dummy.next我个人的习惯是凡是可能删除头节点的链表题一律先加 dummy。这不算性能优化纯粹是让边界处理变简单。刷题时少一个分支就少一个出错窗口。3.4 快慢指针的进阶环形链表入口LeetCode 142 环形链表 II 算快慢指针里比较难的题要返回环的入口节点。结论是快慢指针第一次相遇后把一个指针放回 head另一个保持在相遇点然后两个指针都一次走一步再次相遇的位置就是环入口。网上很多题解直接抛结论没有解释为什么。我当时也困惑了很久后来自己推了一遍假设链表头到环入口的距离是 a环入口到相遇点的距离是 b环的长度是 c。慢指针走了 ab快指针走了 abkck 是快指针绕环的圈数。因为快指针速度是慢指针的两倍所以2(ab) abkc ab kc a kc - b也就是说从相遇点再走 a 步刚好回到入口。这就是为什么放一个指针在 head另一个在相遇点每次走一步相遇点就是入口。理解推导过程以后这种题就不再是死记硬背了遇到变化也能举一反三。4. 滑动窗口双指针的高级形态4.1 窗口模板与无重复字符的最长子串滑动窗口本质上也是两个指针只是它们始终维护一个连续区间。右指针负责扩大窗口左指针负责在条件不满足时收缩窗口。LeetCode 3 无重复字符的最长子串是滑动窗口的入门题。思路是维护一个窗口窗口内不能有重复字符。每加入一个新字符时如果发现重复就把左指针不断右移直到窗口内不再包含重复字符。同时用哈希集合记录窗口内的字符方便判断重复。def length_of_longest_substring(s): window set() left 0 max_len 0 for right, char in enumerate(s): while char in window: window.remove(s[left]) left 1 window.add(char) max_len max(max_len, right - left 1) return max_len关键点在于while循环把窗口收缩到合法状态之后再加入新字符最后再计算长度。为什么顺序不能变因为如果你先算长度再收缩算出来的长度可能包含了重复字符是非法窗口。这个顺序问题我见过很多人在白板上写错。4.2 什么时候收缩窗口什么时候更新答案滑动窗口题最容易迷茫的地方是收缩和更新答案的时机。我总结了一套自己的判断方法如果题目求的是“最长子串/子数组”通常是在窗口合法的时候更新答案不合法时收缩窗口。如果题目求的是“最短子串/子数组”通常是在窗口满足条件时更新答案然后收缩窗口尝试找更优解。比如 LeetCode 76 最小覆盖子串右指针每次扩展窗口直到窗口包含所有目标字符然后左指针收缩同时更新最小长度。注意这里的更新答案发生在收缩过程中因为每次收缩都可能得到一个更短的合法窗口。而最长无重复子串是收缩到合法后再计算窗口长度。很多新手把这两个顺序记反导致“最短的题算出最长最长的题算出最短”。我建议刷这几道题时不要只背模板而是自己拿一个简单用例在纸上走一遍搞清楚每一步窗口里的内容顺序自然就记住了。4.3 滑动窗口的适用边界滑动窗口虽然好用但不是所有跟子串有关的题都能用。核心条件是窗口的合法性必须能通过“加入右边界”“移出左边界”这两种操作维护。举个例子如果题目要求窗口内所有元素互不相同这个条件可以用哈希集合维护可以滑动。但如果题目要求窗口内所有元素之和等于一个固定值并且元素可能是负数那就不能用简单滑动窗口因为负数的存在会让窗口的和既可能变大也可能变小判断条件失去单调性这时候可能要转换思路用前缀和。LeetCode 周赛 430 里我印象比较深的一道题具体题号记不太清了不过思路一致就有点类似这个情况一开始想当然套滑动窗口结果边界条件和负数的存在让窗口判断完全失效。后来转过头来重新分析约束才发现本质上是一个前缀和加哈希的问题。这也是我想强调的滑动窗口是双指针的一种但它不是万能的先判断单调性再使用否则调试到怀疑人生。4.4 滑动窗口的变式固定窗口大小还有一种更简单的形态是固定窗口大小。比如 LeetCode 643 子数组最大平均数 I窗口长度固定为 k你只需要先算前 k 个数的和然后每次右移一位减掉左边滑出的数加上右边新进来的数维护一个总和的最大值即可。这种固定窗口本质上不是快慢指针而是两个指针始终保持固定距离。和链表里的“删除倒数第 N 个节点”有异曲同工之处都是利用间隔固定距离来定位。所以双指针的题型之间其实是有暗线互通的刷到后面你会发现很多技巧只是表达方式不同核心逻辑都是在维护两个位置之间的关系。5. 双指针高频踩坑实录这些细节我花了大量时间才弄明白5.1 去重先收集结果再跳过重复值三数之和这道题的去重我前面已经写了正确版本这里单独复盘一下错误版本。我一开始是这样写的# 错误示范 if total 0: while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 result.append([nums[i], nums[left], nums[right]])我把跳过重复的代码放在了收集结果之前导致什么结果呢比如数组中有两个相同的值我先把左指针跳到了最后一个相同值再把结果收集上来但实际上这可能已经不是当前left和right组合出来的结果了会漏解或者出现错解。正确做法一定是先记录当前有效组合然后再跳过重复值最后再做一次left 1和right - 1把指针移到下一组候选位置。5.2 循环边界还是对撞指针while left right快慢指针while fast and fast.next滑动窗口while char in window这些条件看着简单写错一次就是死循环或者越界。我最常犯的一个错误是在对撞指针里混用。当数组长度为奇数时left right意味着两个指针重合指向的是同一个数。在“找两个数”的语境下这通常是不允许的因为你会拿同一个数当作两个数用。除非题目明确说同一个元素可以用两次否则一律left right。还有链表的快慢指针判断条件一定要先检查fast是否存在再检查fast.next。顺序反了会直接抛空指针异常。正确写法是while fast and fast.next:Python 里and是短路求值先判断fast为真才会判断fast.next这个特性正好用来防止空指针访问。5.3 空输入与单元素边界别小看空输入我有一段时间提交失败的案例十有七八都是因为没处理空数组和单元素数组。数组题空数组直接返回空结果或者 0单元素数组通常也不满足双指针的使用条件要提前判断。链表题head None时几乎所有的指针访问都会报错所以每个双指针函数的第一步都该检查if not head。为什么很多题解里没有单独写这个判断因为有的解法天然覆盖了空输入。比如环形链表我写的if not head or not head.next就同时处理了空链表和单节点链表。但如果你的代码是slow head; fast head.next那空链表直接崩溃。所以不是“要不要处理边界”的问题而是“你的初始化方式决定了需不需要显式处理边界”。5.4 复杂用例的测试顺序我刷题时总结了一套针对双指针问题的自测用例写完之后先跑这些能少提交很多次空数组 / 空链表只有一个元素所有元素都相同已经有序 / 完全逆序答案在两端答案在中间目标不存在大数据量下是否超时比如三数之和如果数组全是 0正确结果应该是[[0,0,0]]而不是无限多个重复答案。如果数组是[1,2,3,4,5]且 target 是 9双指针应该能快速定位[2,3,4]或类似组合。先在心里把这些用例过一遍比直接提交官网测试要高效得多。5.5 哈希表和双指针怎么选很多双指针题用哈希表也能做。比如两数之和的普通版本哈希表是 O(n) 时间和 O(n) 空间双指针加排序是 O(n log n) 时间和 O(1) 空间。两者各有优劣不能因为刷了双指针就强行双指针。我的选择标准很简单如果要求返回下标而且原数组顺序不能动优先用哈希表。如果题目明确说可以排序或者要求的不是下标而是值本身才考虑双指针。如果题目的输入已经有序那双指针是绝对的优先选择。这个选择逻辑在面试里很重要。你说你用的是双指针面试官想听的是你为什么不用哈希表。你把时间和空间的 trade-off 说清楚比直接默写代码更能加分。6. 双指针的刷题策略从母题出发建立题感6.1 母题清单与变式练习如果让我只推荐一组双指针母题我会选这五个LeetCode 167 两数之和 II左右对撞入门LeetCode 15 三数之和去重与嵌套LeetCode 11 盛最多水的容器贪心与移动决策LeetCode 141 环形链表快慢指针入门LeetCode 3 无重复字符的最长子串滑动窗口入门为什么选这五道因为它们分别对应了双指针的三个模型里最典型的场景而且都能作为母题扩散出大量变式。比如会做三数之和四数之和就只是多套一层循环会做环形链表找环入口就只需要多推一个数学公式会做无重复字符的最长子串最小覆盖子串就只是把集合换成计数映射并且调整收缩时机。刷完母题以后我建议按下面这张表做变式练习母题变式题目变化点167 两数之和 II15 三数之和 / 18 四数之和增加嵌套层数与去重逻辑11 盛最多水的容器42 接雨水从单纯移动短边到维护左右最大高度141 环形链表142 环形链表 II加入数学推导找入口19 删除倒数第N个节点876 链表的中间节点从固定间隔改为速度差3 无重复字符的最长子串76 最小覆盖子串 / 209 长度最小的子数组收缩时机和更新答案的时机不同每次做完变式对比母题解法思考哪些地方变了、哪些地方完全没变。这样做的效果比盲目刷 50 道题要好得多。6.2 复杂度分析与口头表述面试的时候代码写完只是第一步把复杂度说清楚同样重要。左右对撞时间 O(n)空间 O(1)排序除外。快慢指针时间 O(n)空间 O(1)。滑动窗口时间 O(n)空间取决于窗口存储结构通常是 O(k)k 是窗口大小或者字符集大小。三数之和这类嵌套时间 O(n^2)空间 O(1)不考虑结果集。这里特别提一下很多人会说滑动窗口是 O(n)这是对的因为每个元素最多被左指针和右指针各访问一次总操作数是 2n 量级常系数不影响复杂度结论。我在周赛复盘时发现如果能主动说出“每个元素最多进出窗口一次所以总复杂度是 O(n)”面试官通常会点点头因为你不是死记复杂度而是理解了指针移动的本质。6.3 题感的建立拿到新题先问三个问题最后分享一个我自己的刷题方法。拿到一道题不管难易先在心里问三个问题输入是数组还是链表是否有序或者是否可以通过排序获得某种单调性问题是找两个数、找一个位置、还是维护一个区间这三个问题的答案几乎能直接定位到双指针的具体分类。数组加有序优先左右对撞链表加位置关系优先快慢指针连续区间加统计条件优先滑动窗口。但这种“题感”不是看出来的是写出来的。我建议你找一个周末把上面的母题每个写两遍第一遍不看任何题解硬写写不出来就看一眼提示然后合上屏幕自己写第二遍隔一天再写重点把去重和边界条件在注释里标出来。做完这个循环你对双指针的理解会有一个肉眼可见的跃升。6.4 从刷题到实际应用的一点延伸刷题的最终目的是面对陌生问题时能快速找到思路。双指针的价值也不只在 LeetCode。比如在业务代码里处理两个有序列表的合并、在日志流里判断某个时间窗口内的事件数量、在链表结构里定位循环引用这些场景底层都有双指针的影子。我自己在实际工程里就遇到过一个问题需要判断某个长字符串里是否存在一个覆盖了所有关键词的最短片段当时第一反应当然是调库扫描后来仔细一想这不就是最小覆盖子串吗直接用了滑动窗口的思路写了一个 O(n) 的版本性能比之前的暴搜快了几个数量级。有时候算法题和业务并不割裂只是换了一层外衣。所以别觉得刷双指针只是为了应付面试。它训练的核心能力是“在看似无序的数据里找到移动的规律”这个能力放到哪里都值钱。如果你现在正好在刷双指针看到某道题卡住不妨停下来想一下它属于哪类模型再用这个系列里的模板去套多半会有新的突破。