1. 为什么学了双指针还是不会做题先分清指针在往哪边跑我估计不少人跟我一样一开始看到双指针这三个字觉得不就是两个下标的事嘛。但实际做题的时候什么快慢指针、左右指针、滑动窗口一会儿一个花样代码写出来不是超时就是越界或者逻辑全对但漏了边界心态直接崩掉。先说我自己的体会。双指针这个技巧本质上是在用两个游标去扫描数据结构把原本需要嵌套循环的 O(n2) 暴力解压到 O(n) 或者 O(n log n)。但它的难点从来不是用两个变量遍历而是搞清楚三个问题两个指针分别承担什么职责指针移动的触发条件是什么循环终止时指针停在哪里这三个问题搞不清楚背再多的模板也没用。我最早就是背模板看到有序数组就套对撞指针看到子串就套滑动窗口结果题目稍微变一下——比如数组里有重复元素、链表有环、窗口要求恰好覆盖某些字符——模板就失灵了。这篇笔记我按实际做题的顺序重新梳理了一遍双指针核心是三种最常见的形态同向快慢指针、对撞指针、滑动窗口。这三种形态覆盖了力扣和面试里绝大多数高频题比如删除有序数组重复项、链表环检测、两数之和、三数之和、盛最多水的容器、无重复字符的最长子串、最小覆盖子串。每道题我都不只给代码还会写清楚指针为什么这么移和我踩过的坑。如果你也处于能看懂题解、但自己写不出来的阶段这篇笔记应该能帮你把双指针从背套路变成想清楚再写。2. 同向快慢指针一个负责探路一个负责占位2.1 原地删除有序数组重复项的完整思路先看最经典的一道LeetCode 26题删除有序数组中的重复项要求原地修改返回新长度。很多人的第一反应是用一个循环遍历发现重复就调用删除操作。Python 里del nums[i]确实能删但删除是 O(n) 的操作整体复杂度直接到 O(n2)而且一边删一边遍历下标还会错位。这时候快慢指针就是标准解法def removeDuplicates(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这里的一个关键理解是slow维护的是一个不重复序列的右边界而fast负责从前往后扫描所有元素。每次发现nums[fast]和nums[slow]不同说明遇到了新值就把这个新值搬到 slow 的下一个位置。这样做的本质是快指针负责探索慢指针负责记录有效区域的终点两者互不干扰。我最初写这道题的时候犯过一个蠢错我把if nums[fast] ! nums[slow]写成了if nums[fast] ! nums[fast - 1]。看似差不多但两者逻辑完全不同——nums[fast] ! nums[fast - 1]确实也能判断当前值是否是新的但这写法的前提是数组有序且重复项相邻。一旦换成无序数组或者要求保留最多 K 个重复项这种变体这种写法就废了。而slow版本的判断天然适应这类变体。2.2 快慢指针检测链表环为什么慢指针走一步、快指针走两步一定相遇链表的环检测是快慢指针的另一个经典场景。力扣141题判断链表是否有环。思路很简单slow一次走一步fast一次走两步。如果链表中存在环那么 fast 最终会追上 slow两者在环内相遇如果无环fast 会先到达链表末尾。def hasCycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False这里有一个值得琢磨的问题为什么 fast 每次走两步而不是走三步、四步关键原因是在环内fast 相对于 slow 的速度是每次一步因为 slow 也在前进。步长差为 1 时fast 不会跳过 slow如果步长差大于 1理论上存在跨越而不相遇的可能性。我在学习这一块的时候做了一个小实验模拟了环长和步长差的关系。以环长 L 为例fast 和 slow 进入环之后两者的距离差会在每次迭代中减少步长差的绝对值。只有当步长差与环长 L 互质或至少满足差值能整除 L 的某个倍数时才能保证一定相遇否则可能会出现永远追不上的情况。实际工程里统一约定 fast 每次走两步不仅因为数学上最稳妥还有一个现实因素链表操作本身开销不大两步足够快没必要用更激进的三步四步反而增加判断fast.next是否为空时的复杂度。2.3 快慢指针踩坑记录口头禅式编码的代价快慢指针常见的陷阱有两个第一个是遍历终止条件的边界。数组类题目通常用for fast in range(len(nums))配合slow 1来写这样终止条件由 for 循环天然管理。但链表类题目必须自己判断fast和fast.next是否为空漏掉任何一个都会导致空指针异常。我见过一个很典型的错误写法while fast.next: # 少了 fast 本身的判空 slow slow.next fast fast.next.next如果fast已经指向空节点了fast.next就抛异常。更隐蔽的做法是只写了while fast而漏掉fast.next当 fast 恰好停在最后一个节点时fast.next.next直接报错。正确写法必须同时判断fast和fast.next。第二个陷阱是把快慢指针和普通双下标混淆。快慢指针在数组去重场景中更像是双下标覆盖在链表环检测中才是真正意义上一快一慢的移动。写代码前先确认自己用的是哪个场景代码风格和边界判断完全不同。3. 对撞指针缩小区间的正确姿势与两个经典问题3.1 两数之和的对撞解法从暴力到 O(n) 的关键一跃LeetCode 167题在一个有序数组中找到两个数使它们的和等于目标值。暴力解法是双重循环O(n2)。但一旦抓住了有序这个特性就可以用对撞指针左指针left指向数组开头右指针right指向数组结尾每次计算nums[left] nums[right]和等于 target直接返回和小于 target说明左边数太小left 1和大于 target说明右边数太大right - 1def twoSum(numbers, target): left, right 0, len(numbers) - 1 while left right: cur numbers[left] numbers[right] if cur target: return [left 1, right 1] # 题目要求从1开始计数 elif cur target: left 1 else: right - 1 return [-1, -1]这个算法的正确性论证非常有意思我来说说为什么可以放心地移动指针而不会漏掉解。初始时指针覆盖整个区间。如果cur target说明当前左端元素太小。如果右移left相当于舍弃了当前left这个元素与所有剩余元素配对的可能性但因为我们确保left之前的元素都已经被扫过而且它们与任何位置的元素配对都不可能等于目标值因为此时连最大的右端元素配上都不够 target所以可以安全舍弃。判断是否安全舍弃就是对撞指针的核心思维。每次移动指针其实都是在做一次排除法而且排除的依据是数组有序性和当前区间边界。我在笔记里画了一个区间收缩的例子数组[2, 7, 11, 15]target9。初始 left0, right3和是17大于9所以右指针左移到11此时和是13继续左移到7此时和是9直接返回。整个过程只走了三次判断。3.2 三数之和的完整去重流程对撞指针的进阶形态LeetCode 15题三数之和要求找出所有三元组且不允许重复。三数之和对两数之和做了一层改造先固定一个数nums[i]然后在剩余区间里用对撞指针找两个数使nums[left] nums[right] -nums[i]。这样就把三数之和拆成了固定一个 两数之和。但仅仅这样做会得到大量重复三元组。比如数组[-1, 0, 1, 2, -1, -4]如果不在外层循环里去重你会得到两个[-1, 0, 1]一个从i0出发一个从i4出发——这显然不对。去重的标准做法是在两个地方做外层固定数的循环里如果nums[i] nums[i - 1]直接跳过避免同一首个数字重复处理。内部对撞指针找到一组解后把left和right都移动到不重复的位置确保同一对指针不会输出重复组合。def threeSum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue if nums[i] 0: break # 因为数组已排序第一个数大于0就说明后续更不可能 left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: 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 elif total 0: left 1 else: right - 1 return res写这道题时我掉进过一个非常经典的坑忘了排序。如果数组不是有序的对撞指针靠着区间端点的大小关系来做排除法这个前提就完全失效。我第一次刷三数之和时直接拿原始数组去跑指针移动逻辑完全错乱输出结果乱七八糟。后来才意识到对撞指针只适用于有序序列或本身就有大小顺序结构比如 BST 的中序序列任何用到左边界小、右边界大这个前提的题目先排序永远是第一步。3.3 盛最多水的容器移动指针的直觉反直觉推理再来一道对撞指针的应用题LeetCode 11题盛最多水的容器。给你一个高度数组找到两条线构成的容器能装最多水的面积。暴力解法是枚举所有下标对计算min(height[left], height[right]) * (right - left)O(n2) 显然会超时。对撞指针的做法如下def maxArea(height): left, right 0, len(height) - 1 res 0 while left right: cur min(height[left], height[right]) * (right - left) res max(res, cur) if height[left] height[right]: left 1 else: right - 1 return res为什么可以移动较矮的那一边直觉推理是这样当前容器的容量受限于较矮的那根柱子。如果移动较高的一边新的容器高度无论如何都不会超过原来较矮的那个高度因为决定高度的总是矮的一端同时宽度还在缩小容量只可能变小或不变。反过来移动较矮的一边虽然宽度也缩小了但高度可能因为新柱子变高而增加所以存在让面积更大的机会。这个推理有一个非常反直觉的地方移动较矮的一边到下一个位置时我们是在丢弃这个矮柱子与所有右侧柱子配对的可能。但为什么是安全的因为假设当前右边柱子很高这个矮柱子与任何右侧柱子配对的容量上限都以这个矮柱子高度为准而当前这个配对已经取到了最大宽度右指针在最远端。所以只要当前矮柱子的高度不变宽度在缩小后面所有和它配对的容量都不会超过当前值。因此可以放心地把矮的那端往中间移动。这种反直觉但严密的推理在双指针题里非常多见我强烈建议不要只靠感觉来接受最好自己拿几组测试数据验证一遍。4. 滑动窗口同向指针进化版处理连续子序列的利器4.1 无重复字符的最长子串窗口扩张与收缩的节奏说到滑动窗口力和扣上最典型的是 LeetCode 3题无重复字符的最长子串。之前我总觉得滑动窗口和快慢指针很像都是两个同向指针但它们的核心逻辑并不一样。快慢指针更关注覆盖和占位滑动窗口关注的是维护一段满足条件的连续区间。用双指针实现滑动窗口时left是窗口左边界right是窗口右边界。我用一个字典记录窗口内每个字符最后一次出现的位置。当右指针遇到一个重复字符时就把左指针直接跳到重复字符上一次出现位置的下一个位置这样窗口内就不会有重复字符了。def lengthOfLongestSubstring(s): pos {} left 0 max_len 0 for right, ch in enumerate(s): if ch in pos and pos[ch] left: left pos[ch] 1 pos[ch] right max_len max(max_len, right - left 1) return max_len这段代码里最关键的是pos[ch] left这个判断。我看过很多版本没有这个条件直接写if ch in pos但那样会出错——因为pos里存的是字符历史出现过的位置有些位置可能在当前左边界之外已经不属于当前窗口了。举个例子字符串abba当 right 走到最后一个 a 时pos[a]还是 0但当前的窗口左边界已经因为 b 的重复移动到了 2此时 a 的下标 0 根本不在窗口内不能作为重复依据。这个细节我强烈建议每一位学习者都手动走一遍。我在面试时就被问到这个判断的意义如果答不上来面试官会认为你只是背了代码而不是真正理解滑动窗口。4.2 最小覆盖子串收缩时机决定一切LeetCode 76题最小覆盖子串是滑动窗口里难度较高的一道要求找到 s 中包含 t 所有字符的最短子串。这里的基本思路是先用右指针扩大窗口直到覆盖 t 中所有字符然后尝试移动左指针收缩窗口在仍然覆盖 t 的前提下找最短子串。这样窗口在扩张—收缩—扩张—收缩的循环中前进每个字符至多被左右指针各访问一次整体 O(n)。def minWindow(s, t): from collections import Counter need Counter(t) missing len(t) left 0 res min_len float(inf) for right, ch in enumerate(s): if need[ch] 0: missing - 1 need[ch] - 1 while missing 0: # 窗口已覆盖所有目标字符尝试收缩 if right - left 1 min_len: min_len right - left 1 res s[left:right 1] chl s[left] need[chl] 1 if need[chl] 0: missing 1 left 1 return res这个写法用missing变量记录还差多少个字符才算覆盖。注意这里的need字典对不属于 t 的字符也做了减法和加法但这其实是无害的因为只有当need[ch] 0时missing才会变化。判断是否收缩的时机是missing 0一旦窗口内的字符覆盖了 t立刻尝试收缩左边界。我最初看到一个版本的计数器逻辑直接用need[ch] 0来判断当前字符是否为所需字符思路也是对的但在字符种类很多的情况下略显绕。missing的做法更直观也方便调试。4.3 滑动窗口的两个常见误区第一个误区是窗口内计数信息的更新时机。拿最小覆盖子串来说很多人会在右指针移动时更新need却在左指针移动时忘掉need的还原导致窗口状态失真。其实左右指针移动时都要同步修改need因为你的窗口边界变了字符计数自然要跟着变。第二个误区是用是否存在重复类题目去硬套覆盖类题目的模板。无重复字符最长子串的重点是维护不重复最小覆盖子串的重点是维护覆盖。两者虽然都是滑动窗口但收缩触发条件完全不同。前者遇到重复立刻收缩后者只有在完全覆盖后才能收缩而且收缩后还要继续验证覆盖状态。想通这一点滑动窗口类题目基本就不会懵了。5. 双指针的复杂度、适用场景与三个容易搞混的点5.1 为什么双指针能做到 O(n)摊还分析的直观理解双指针题目的时间复杂度看起来是两重循环比如滑动窗口里的 while 嵌套 for实际上每个指针在每个循环里只移动一次。整个过程下来left和right分别最多移动 n 次总操作次数不超过 2n因此复杂度是 O(n)。这种分析方法叫摊还分析。通俗理解就是哪怕代码看起来像嵌套循环只要每个指针在每个单位时间里只移动一次、且指针从不回头整体扫描次数就是线性的。我把这个结论贴在笔记里提醒自己以后遇到双指针题别看到 while 嵌套就以为复杂度是 O(n2)先数一数每个指针一共移动了多少次。5.2 什么时候选用双指针、什么时候该选哈希或二分双指针不是万能的。在有序数组中找两数之和双指针是标准答案但如果是无序数组的两数之和哈希表明显更合适复杂度同样是 O(n)且不需要额外排序。来看一道题力扣1题两数之和数组无序要求返回下标。用哈希是最直接的def twoSum(nums, target): seen {} for i, num in enumerate(nums): if target - num in seen: return [seen[target - num], i] seen[num] i return []你可能会问那先排序再用对撞指针行不行可以但排序的时间复杂度是 O(n log n)而且排序会丢失原下标信息如果题目要求返回原下标排序后的数组还得额外记录原位置反而更麻烦。所以我的选择经验是数组有序优先考虑对撞指针。数组无序但只关心值不关心位置可以先排序再对撞。数组无序且必须返回原下标直接哈希。连续子串、子数组的最值问题滑动窗口。链表环检测、链表中点快慢指针。这个决策流程看起来简单但真正做题时能帮你节省大量试错时间。5.3 双指针不适合哪些场景双指针不适合的场景主要有三类第一类是需要输出所有组合但组合数量本身就很大的题目。比如找出所有和为 target 的四元组即使双指针能做到 O(n3)实际输出数量可能非常大这时候算法的瓶颈不在查找而在输出。第二类是数据源不是线性结构的时候。双指针通常作用于数组、链表这类线性结构一旦换成树、图双指针就基本用不上了。树上的常见技巧是 DFS 或 BFS图的环检测要用拓扑排序或 DFS 标记而不是简单的快慢指针。第三类是字符串匹配类的复杂模式匹配。比如正则表达式匹配、单词接龙这类滑动窗口无法处理复杂的约束关系这时候该用动态规划或 BFS。判断能不能用双指针最核心的标准只有一个问题能否通过指针的单调移动永不回头来逐步缩小搜索范围或维护有效区间。如果你发现指针在某些情况下必须回头或重新扫描那大概率不适合直接用双指针。5.4 双指针与二分查找的相似与不同对撞指针和二分查找都依赖有序数组都通过缩小搜索区间来定位答案但它们的目标完全不同。二分查找是在单调区间内找某一个特定值或边界每次直接丢弃一半区间对撞指针是同时从两端出发逐步逼近每次只丢弃一个端点适用于找一对元素满足某种关系的场景。举个容易混淆的例子有序数组中找 target 的插入位置用二分有序数组中找两个数之和等于 target用对撞。前者需要的是单点定位后者需要的是双元素关系。如果把两者搞混代码要么多此一举要么直接失去有序性优势。6. 把双指针用到面试和工作中我的三个实战观察最后想聊一点面试和工作层面的实际体会。第一面试中遇到双指针题先把指针职责说清楚再写代码。比如面试官问怎么找有序数组中和为 target 的两个数你上来就写 while 循环万一写错很难看出思路。但如果你先说左指针维护当前最小元素右指针维护当前最大元素和小于 target 就把左指针右移和大于 target 就把右指针左移面试官一眼就知道你有清晰的分析能力。码农界有句话叫Code tells how, comments tell why双指针题的why就是指针移动的依据这点比代码本身重要得多。第二边界条件要用小规模用例主动验证。我刷题这些年最大的进步来自于养成了写完代码立刻用空数组、单元素数组、元素全相等数组、目标值比所有元素都大/都小这五组用例去自测的习惯。很多边界 bug 在这样的自测下无处遁形。比如三数之和的nums[i] 0提前 break 这个优化如果没有全正数组的测试用例你可能根本不会发现它可以提前终止循环。第三双指针思想在业务代码里也有用武之地。我处理过一个日志合并的需求两个按时间排序的日志文件需要合并成一份按时间排序的总日志正好可以用两个指针分别指向两个文件的当前行谁的时间戳小就输出谁然后移动对应指针。这种场景不需要任何框架双指针的思想直接就能落地。类似地合并两个有序数组力扣88题在业务中经常以合并两个配置文件、合并两份统计数据的形式出现。这些观察也许不如刷题模板直观但我觉得一个算法技巧真正内化的标志是你能在脱离算法题库语境后还能在真实数据面前本能地想到它。双指针就是这样一种既简单又狡猾的技巧简单在思想狡猾在边界。多看多练多想比死记硬背任何一个模板都管用。