双指针技巧全解：对撞、快慢指针与滑动窗口的Python实战

写这篇笔记之前我先交代个背景上一篇我已经把双指针的基本概念和几道入门题过了一遍这篇算是进阶版的第二篇。如果你正在刷LeetCode或者准备算法面试双指针绝对是你绕不开的一个技巧——它能把很多O(n^2)的暴力解法压到O(n)而且代码量通常不超过二十行配合Python的列表和链表操作写起来非常顺手。但它又是一个特别容易“看着会、写着错”的知识点循环边界差一个等号、指针移动顺序反了结果就完全不对。这篇笔记我重点讲三件事双指针的三种形态怎么识别、每种形态的Python实现有哪些容易踩的坑、以及五个典型场景的完整代码和拆解。内容偏实战建议你打开编辑器跟着敲一遍。1. 双指针的三种基础形态双指针本身不是某种高深的数据结构它只是一种“用两个指针协同移动来减少遍历次数”的解题思路。根据指针的移动方式我习惯把常见场景分成三类。一开始刷题的时候我总想硬套模板后来发现关键是先判断题目属于哪一类再套对应套路效率会高很多。1.1 对撞指针从两端向中间夹逼对撞指针的典型特征是“数据有某种单调性”比如有序数组。一个指针放在最左端一个放在最右端每一轮根据当前两个指针指向值的比较结果决定移动左边还是右边。这种策略的核心逻辑是当前组合已经不可能产生更优解时就果断放弃这一侧。我用一个特别直白的例子说明为什么它高效。假设有一个有序数组要找出两个数之和等于目标值。暴力做法是双重循环枚举所有数对时间复杂度O(n^2)。但对撞指针每一轮只移动一个指针左右指针总共移动n次时间复杂度变成O(n)。关键在于数组有序那么left指向的值是当前可用最小值right指向的值是当前可用最大值。两者之和大于目标值说明right不能再和任何更左边的值组合出更小的和所以right必须左移反之则left右移。每一轮都能排除一整批不可能的组合。判断对撞指针的标志就一句话题目涉及“在一段序列中找满足某种条件的两个元素”并且这段序列整体有序或者可以通过排序变得有序。典型题目包括两数之和有序数组版、回文串判断、反转数组、盛最多水的容器。1.2 快慢指针一快一慢追踪轨迹快慢指针的经典场景是链表一个指针每次走一步另一个每次走两步。如果存在环两个指针最终会相遇如果不存在环快指针会先到达链表尾部。除了检测环它还可以用来找链表的中点、倒数第k个节点甚至判断回文链表。这种思路的生活化类比是操场跑步两个人同向出发一个跑得快一个跑得慢如果跑道是环形的跑得快的人迟早会追上跑得慢的人。如果跑道有终点快的人先到终点。慢指针每一步都在“记录轨迹”快指针则负责“探索前方”两者配合就能在O(n)时间内完成对链表的性质判断。在数组类题目中快慢指针还有一种同向变体快指针负责遍历整个数组慢指针负责“覆盖”符合条件的位置。比如删除有序数组中的重复项快指针探索慢指针指向下一个不重复元素应该写入的位置。这种写法优点是原地完成空间复杂度O(1)。1.3 滑动窗口连续区间的移动窗口第三种形态是滑动窗口本质上是两个指针维护一个连续区间快指针扩展右边界慢指针收缩左边界。它与前两种最大的区别是指针始终只向右移动而且窗口内的状态是“连续维护”的每一轮都基于上一轮的窗口状态做增量更新而不是重新计算。这种模式专门处理“连续子数组/子串”问题比如找最长无重复子串、最小覆盖子串、长度最小的子数组。暴力解法是枚举所有子区间O(n^2)滑动窗口让每个元素最多被左指针和右指针各访问一次整体O(n)。画个图更好理解想象一条拉链右边链齿不断前进左边链齿根据条件决定是否跟上来拉开的开口始终是一个连续区间。判断滑动窗口的标志也很明显题目里出现“连续”两个字并且要最大化或最小化某个关于窗口的指标。到这里你应该能感受到双指针不是什么玄学它就是在“数据有序”或“数据可增量维护”的前提下用两个指针替代一层枚举。2. Python实现双指针的边界与细节很多同学双指针思路完全正确一到写代码就报错或者结果不对。我总结了一下绝大多数问题出在循环边界、指针移动时机和状态更新这三块。这一节我会把每个坑拆开讲清楚。2.1 循环条件left right还是left right这是最经典的坑没有之一。对撞指针的标准模板是left, right 0, len(nums) - 1 while left right: ... left 1 right - 1但很多场景用的是while left right。怎么判断核心是看题目最后需要处理的是“两个不同位置的元素”还是“区间本身”。如果题目要求两个不同的元素比如两数之和、盛水容器用left right因为left等于right时指向的是同一个元素不符合题意而且通常此时已经无需再处理。如果题目要求“判断整个序列是否满足某种性质”指针可能会在中间相遇并需要处理中间位置本身用left right比如二分查找、反转数组这类。我自己的习惯是先想清楚“当left和right指向同一个位置时这个元素还需不需要处理”。需要就写不需要就写。这个判断方法比死记硬背靠谱得多。2.2 指针移动的顺序和时机指针移动的顺序看起来简单写错的人却特别多。核心原则是先判断当前状态再决定移动哪个指针最后才移动指针。很多人习惯先移动再判断或者两个指针同时移动导致结果错乱。以对撞指针为例while left right: total nums[left] nums[right] if total target: return [left 1, right 1] elif total target: left 1 else: right - 1这里每一轮只移动一个指针绝不同时移动两个。因为当前组合不满足条件时另一个指针的状态可能仍然是“有用”的需要等下轮继续判断。快慢指针同理快指针先走两步慢指针再走一步然后才做比较。滑动窗口则是“先尝试扩大右边界再根据条件收缩左边界”顺序反了会直接导致窗口缺失元素。2.3 让代码更好读的三个习惯第一变量命名直接用left和right不要用l、r、i、j。算法题虽说不限制变量名但面试时你要边写边解释全用单字母会让对方很难跟上。第二指针更新语句单独一行不要和条件判断挤在一起方便调试时打点。第三涉及滑动窗口时把“窗口状态的更新”集中放在一个区域用注释标记“扩展右边界”和“收缩左边界”这样一旦结果不对排查范围立刻缩小。另外还有一个Python特有的小建议能用enumerate就用enumerate尤其是滑动窗口里需要同时用到索引和值的时候比手动维护right再取值要少一个出错点。3. 五个经典场景完整实现这一节是全文的重头戏。我选了五道覆盖三种形态的典型题目从最简单的开始每道都给出完整代码、关键行解释和复杂度分析。建议你按顺序读每道题读完就自己敲一遍。3.1 有序数组两数之和对撞指针入门题目是LeetCode 167输入是一个升序数组和一个目标值要求返回两个数的下标。注意题目的下标从1开始计数返回时需要加1。def two_sum(numbers, target): left, right 0, len(numbers) - 1 while left right: total numbers[left] numbers[right] if total target: return [left 1, right 1] elif total target: left 1 else: right - 1 return []这段代码的关键点在while left right。为什么用因为题目要求两个不同位置的元素当left等于right时两者指向同一个数组合没有意义。再看移动逻辑和小于目标值说明当前左指针太小它和任何右指针右边的元素相加都不可能更大数组有序所以左指针右移和大于目标值说明当前右指针太大它和任何左指针左边的元素相加都不可能更小所以右指针左移。每一轮都排除掉一整个方向的组合。时间复杂度是O(n)空间复杂度O(1)。这道题我见过有人用哈希表写也能过但需要O(n)的额外空间。在“有序”这个条件下双指针是更优解这也说明了双指针的本质利用数据本身的顺序特性省去枚举。3.2 删除有序数组重复项同向快慢指针LeetCode 26输入一个有序数组要求原地删除重复元素返回新长度。这是同向快慢指针的典型场景。def remove_duplicates(nums): if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 1慢指针永远指向“已经处理好的不重复序列的最后一个位置”快指针负责探索新元素。每次快指针发现一个和慢指针指向值不同的元素就把慢指针前进一步并把新值写进去。因为数组有序相等元素一定连续排列所以不需要额外空间去重。边界条件是空数组必须单独处理否则nums[0]会越界。这里slow从0开始返回值是slow 1因为长度等于最后一个不重复元素的下标加1。很多人在这一步算错比如数组是[1,1,2]slow最终停在1长度就是2正好是slow 1。时间复杂度O(n)空间O(1)。这道题是同向双指针中最好理解的一道建议先把它的思路彻底吃透因为后面很多数组原地操作的题目都是这个套路。3.3 环形链表检测快慢指针经典应用LeetCode 141给定一个链表判断是否有环。经典解法是快慢指针def has_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False关键在于while fast and fast.next这个条件。如果链表没有环快指针会先到达尾部但它是每次走两步所以不仅要判断fast本身不能为空还要判断fast.next不能为空否则下一次执行fast.next.next就会报NoneType错误。这是链表双指针最容易翻车的地方。如果有环快指针每次走两步慢指针走一步两者距离每轮缩短1最终一定相遇。有人可能会问为什么快指针每次走两步而不是三步两步就可以保证“追及速度差为1”一定能相遇如果三步“速度差为2”理论上也能追上但要考虑跳过头的情况代码复杂度更高收益却没增加。所以面试里写两步就够了。这道题还有一个进阶版本LeetCode 142返回环的入口节点在快慢指针第一次相遇后把一个指针移回链表头两个指针以相同速度同步前进再次相遇的位置就是环的入口。原理涉及一点数学推导这里不展开但强烈建议自己推导一遍能帮你彻底理解快慢指针的位移关系。3.4 无重复字符的最长子串滑动窗口LeetCode 3给定一个字符串找出不含重复字符的最长子串的长度。这是滑动窗口入门的头号题目。def length_of_longest_substring(s): char_index {} left 0 max_len 0 for right, ch in enumerate(s): if ch in char_index and char_index[ch] left: left char_index[ch] 1 char_index[ch] right max_len max(max_len, right - left 1) return max_len思路拆开讲右指针每轮向窗口纳入一个新字符如果这个字符之前出现过并且上一次出现的位置在窗口内也就是char_index[ch] left说明窗口里现在有重复字符了就需要把左指针跳到重复字符上一次出现位置的右边从而让窗口重新变“干净”。无论是否发生跳跃都要更新这个字符的最新位置并更新最大长度。char_index[ch] left这个判断是整道题最容易忽略的细节。不加这个条件的话你会遇到这种情况字符a在位置0出现过后来左指针已经跳到了位置5窗口里根本没有a但你还认为a是重复的于是错误地收缩窗口。保证了我们只处理“位置仍然在当前窗口内”的历史记录。这道题的时间复杂度是O(n)空间复杂度O(字符集大小)因为哈希表最多存储所有不同字符的位置。Python里字符串的enumerate同时给出下标和字符配合窗口使用非常顺手。3.5 最小覆盖子串带条件的窗口收缩LeetCode 76这道题是滑动窗口里难度中上的题给定字符串s和t在s中找到包含t所有字符的最短连续子串。它是前面第3.4题的自然延伸但窗口收缩的条件更复杂。这里用“缺失计数”的思路def min_window(s, t): from collections import Counter need Counter(t) missing len(t) left 0 ans (0, float(inf)) for right, ch in enumerate(s): if need[ch] 0: missing - 1 need[ch] - 1 if missing 0: while left right and need[s[left]] 0: need[s[left]] 1 left 1 if right - left ans[1] - ans[0]: ans (left, right) need[s[left]] 1 missing 1 left 1 return s[ans[0]:ans[1] 1] if ans[1] ! float(inf) else 核心逻辑need记录每个字符还需要多少个missing记录还缺多少个字符。右指针每纳入一个字符就消耗一个配额。这里有个trick对不在t里的字符need[ch]会变成负数它表示“这个字符是多余的”正好用来判断收缩条件。当missing变成0时说明当前窗口已经覆盖了t接下来要做两件事一是尝试收缩左边界把左边多余字符need为负的全部排除二是记录当前窗口长度。记录完后主动移除左边第一个必要字符并破坏覆盖状态让missing变回大于0然后右指针继续前进寻找下一个窗口。这套流程看起来复杂本质就是“维护状态 不缺了就收缩换答案 主动破坏状态继续找”。哈希表Counter的好处是自动把缺失字符初始化为0不存在的字符访问时也返回0省去了手动初始化的代码量。但要注意need[ch]为负的语义——它不代表“还需要负数个”而是代表“当前窗口里多了几个”。理解这一点这道题就算真懂了。4. 常见问题排查与调试实录双指针代码量小但调试起来常常让人抓狂。我把实战中遇到最多的几类问题整理成一个列表附上排查思路和解决方案。这一节的内容是我踩坑踩出来的比很多题解写得更直白。4.1 死循环与数组越界最典型的死循环是条件判断写对了但指针更新写错了位置或者某个分支忘记了更新指针。比如对撞指针中你写了total target时right - 1一旦这个条件不成立左右指针都不动循环就永远执行不完了。排查方法很简单在循环体开头打印left和right运行三个测试用例就能看到指针冻结在哪个位置。数组越界则多见于快慢指针访问链表的场景。链表快慢指针的标准错误是while fast.next and fast.next.next这个顺序是错的——如果fast本身已经是None直接访问fast.next马上抛异常。正确做法是先判断fast再判断fast.next。Python初学者经常忘记这一点跑起来直接AttributeError。4.2 窗口状态更新的典型错误滑动窗口的状态更新比指针移动更容易出错。最常见的错误是左指针收缩窗口时忘记把“被移除字符”的计数恢复。比如最小覆盖子串那道题你在s[left]离开窗口时没有执行need[s[left]] 1后续窗口的missing计算结果就会失真可能提前判断“已经覆盖”也可能永远判断不了“覆盖”。另一个高频错误是哈希表只在特定条件下更新却要求它在所有轮次都反映最新状态。记住一个原则右指针每纳入一个字符count必须更新左指针每移出一个字符count必须恢复。这两条是无条件的和当前窗口是否满足条件无关。4.3 我的调试三板斧第一板斧是“打印窗口快照”每次左右指针移动后打印left、right以及当前窗口的内容。这能让你直观看到窗口的变化是否符合预期。第二板斧是“构造极简测试用例”空输入、单元素输入、全部相同元素、全部不同元素这四个用例覆盖了绝大多数边界bug。第三板斧是“手动模拟一遍再跑代码”找一张草稿纸把一个短输入的例子从头到尾走一遍把指针移动的每一步画出来然后和代码实际输出对比。这看起来笨但我实测是解决“思路对但写不对”的最快方法。调试过程中如果发现结果差一点不是整体错乱优先怀疑“边界条件差1”比如和混用、left 1还是left。如果结果完全胡说八道优先怀疑状态更新逻辑尤其是哈希表和计数器。5. 写在最后的经验双指针学起来并不难难的是快速判断一道题能不能用双指针。我个人在实战中的经验是先看数据是否有序或者能否维护出单调关系再看题目是否涉及连续区间或成对元素。这两个特征只要占一个就可以尝试用双指针去替换显式枚举。初期刷题别急着追求最优解先把暴力解法写出来再问自己“哪一层循环是多余的”想明白这个问题双指针的引入点就找对了。还有一个小技巧题目做多了之后把同形态的题放到一起比较比如把双指针的题按“对撞、快慢、滑动窗口”分类存档久了之后看到新题就能条件反射地归类这比单纯刷题数量要有效得多。