刷题这几年有一类技巧几乎每晚都会遇到从简单的数组遍历到复杂的字符串处理从链表判断到子串查找它都能横插一脚而且大多数时候是最优解——我说的就是双指针法。很多朋友在刚接触算法时会把双指针当成“一个技巧”来记看到有序数组就用对撞看到链表就问快慢看到子串就套窗口。这种背模板的学法很容易翻车因为双指针法本质上不是一套固定招式而是一种“利用两个游标互相配合、减少无效枚举”的思维范式。本文我会把双指针法的三种基本形态、每种形态的适用边界、代码模板和常见坑位全部拆开来讲并结合我从笔试面试和日常开发中积累的真实案例给你一套可以直接上手使用的判断框架。无论你是准备校招笔试还是在工作中突然要手写一个字符串处理函数这篇文章都能帮你少走很多弯路。这篇文章不是概念复述我默认你至少写过循环知道数组下标是什么。我会从“为什么要用双指针”讲起再把对撞指针、快慢指针、滑动窗口这三板斧逐一展开配完整代码和复杂度分析最后给一份排错速查表。读完你再看任何双指针题应该会下意识去想“这两个游标各自承担什么职责”而不是急着百度题解。1. 双指针的整体设计为什么它能省下整整一个数量级1.1 单指针的困境暴力枚举到底浪费了什么先看一个最常见的场景。给你一个升序排列的数组找出两个数让它们的和等于目标值。最直觉的做法是两层循环固定一个数去后面线性查找另一个数。这种做法在数组长度 n 等于 10 万时最坏要执行约 50 亿次比较在 OJ 上基本注定超时。为什么这么慢因为它在做“盲目搜索”。你在固定第一个数以后其实已经知道了第二个数的取值区间目标值减去当前数剩下的小于等于它的部分才有意义。但暴力解法仍然把这部分和更大的部分一视同仁地扫过去制造了大量无效比较。这里浪费的核心是“信息”排序数组本身携带了结构信息而你压根没利用它。我早年刷题时最常犯的毛病就是这样拿到题先写两个 for 循环跑得通就提交跑不过就开始玄学换方法。后来我才意识到所谓算法优化就是把“你已经知道的事实”转化为“你不再去做的计算”。双指针就是这种转化最典型的工具。1.2 两个游标把 O(n²) 压成 O(n)本质是压缩解空间双指针法的核心设计是让两个指针在遍历过程中每一轮都可靠地排除掉一批“不可能产生答案”的候选解。还是拿有序数组两数之和举例。左指针指向开头右指针指向结尾算出当前和。如果当前和大于目标值说明右指针指向的元素太大了而且因为数组升序右指针右边不可能有更小的元素来补救所以右指针必须左移一步。如果当前和小于目标值说明左指针指向的元素太小了只能让左指针右移一步。每走一步我们就排除了一个元素成为正确答案的可能性。整个过程左指针最多走 n 步右指针最多走 n 步总步数是 2n复杂度 O(n)。从解的集合角度理解暴力法的解空间是一个 n×n 的矩阵双指针每移动一次就划掉一整行或一整列。这个“划行划列”的动作是双指针法所有变体的共同底层逻辑。理解了这一点你在面对任何可以用双指针解决的题目时都会自然地追问这道题里两个指针各自代表着哪一维的枚举移动任何一个指针能不能保证排除掉一个无解区域能就可以用双指针不能题目大概率有诈。1.3 三种形态的判断框架先看数据结构再定游标职责双指针法有三大常见形态我按照工作中实际遇到的频率排序给你一个特征对照表形态典型数据特征指针运动方向典型应用对撞指针数组有序或回文类一左一右相向而行两数之和、三数之和、盛水容器、回文判断快慢指针链表或环形结构一快一慢同向而行环形链表检测、链表中点、倒数第 k 个节点滑动窗口连续子串/子数组一左一右同向追赶无重复最长子串、最小覆盖子串、长度最小子数组这个表不是用来背的而是帮你建立第一反应。看到有序数组优先想对撞看到链表优先想快慢看到“连续子串”“连续子数组”这种限定词基本就是滑动窗口。但注意这个表只是入场提示不是答案。我遇到过很多把滑动窗口解法硬套到“非连续”场景上的同学最后代码写得比暴力还长。双指针类题目的核心从不是“用哪个模板”而是搞清楚两个指针各自的状态语义这个走了那边该怎么动动了以后状态还成不成立。后面几节我会针对每个形态逐一说透。2. 核心细节边界条件、移动规则与循环不变量2.1 循环边界while (left right) 还是 差之毫厘谬以千里很多初学者被一道题卡住不是因为思路不对而是把 left right 写成了 left right然后莫名其妙地死循环或漏解。这里我直接给你一条判断经验当两个指针指向的元素不能是同一个时典型如“找两个不同位置的下标”用 left right。当两个指针指向的元素可以是同一个时典型如“判断回文时单个字符本身是回文”用 left right。举个例子两数之和里你不能用同一个元素当两个数所以循环条件是 left right而在验证一个字符串是不是回文时不论中缝是单个字符还是没有字符都需要检查完再退出所以是 left right。这个判断其实有一个更底层的依据你定义的循环不变量是什么。如果循环体内部要求“left 和 right 必须指向两个不同的位置”那么 left right 是硬约束如果循环体内部允许 left 和 right 指向同一个位置时继续判断那么把 left right 当作边界就是安全的。我调试这类问题时的土办法很简单把循环边界写出来然后代入最小的测试用例做手工模拟。比如数组长度为 2 的两数之和left0right1循环体执行一次后 left1right0 或 left0right-1此时如果写 left right就会多执行一次无意义甚至越界的比较。手动模拟三分钟比记忆“什么时候用 ”要靠谱得多。2.2 指针移动规则该谁动就动谁别让另一个指针背锅双指针题里最常见的低级错误是把两个指针的移动条件写反。这背后通常是“我模糊地知道该移动指针但说不清为什么是该移动它。”我建议每次写代码前先在心里回答一个问题当前这个局面下哪一个指针移动之后能保证永远不会漏掉正确答案另一个指针的移动是前面那个移动的必然结果而不是并列选择。以对撞指针的“盛最多水的容器”为例left 指向左挡板right 指向右挡板容量 min(height[left], height[right]) × (right - left)。如果 height[left] height[right]那么只要 left 不动无论 right 怎么往左挪容量都不可能超过当前的 min 值乘以更小的宽度。换句话说以 left 为左挡板的容器最优解就是当前这个了所以 left 必须右移去测试新的左挡板。这里 right 的移动只是左边移动的结果绝不是先决条件。刷题时我有个习惯在代码旁边注释掉一行“为什么这个指针动”每次都写。别小看这个动作它能逼你把模糊的直觉变成清晰的逻辑也能在你下次回看代码时省下大量回忆成本。2.3 循环不变量定义好“已处理区域”和“待探索区域”双指针代码里维护一个清晰的“区域划分”极其重要。我经历过很多次“跑一遍对跑两遍错”的诡异情况最后定位到的问题几乎都是指针语义在循环中悄悄变了但代码还在按老语义去更新答案。以同向快慢指针的“移动零”为例slow 指针左侧不包含 slow是“已经处理好的非零序列”fast 指针是“正在扫描元素”fast 右侧是“尚未探索区域”。整个循环的不变量是任意时刻[0, slow) 区间内都是非零元素且顺序与原始顺序一致。只要这个不变量成立最后把 [slow, n) 全部填零就一定正确。写这类代码时我建议你在纸上画出三个区域标注清楚“处理过”“正在处理”“没处理”然后让代码里的每一步移动都恰好对应一个区域边界的推进。一旦代码的某一步既移动指针又同时破坏了区域定义那就是 bug 的温床。调试这类问题不要只看打印的数组中间状态要对着不变量逐行核此刻 slow 之前真的是“非零且保序”吗如果是继续如果不是说明上一轮就错了。3. 四类经典题型的完整实现与解析3.1 对撞指针有序数组的两数之和与三数之和先看两数之和。给定升序数组 nums 和目标值 target返回两个数的下标或数值。代码骨架如下def two_sum(nums, target): left, right 0, len(nums) - 1 while left right: cur nums[left] nums[right] if cur target: return [left, right] elif cur target: left 1 else: right - 1 return [-1, -1]这段代码里有三个细节值得展开。第一为什么 left right 而不是 因为题目要求的是“两个数”同一个下标不能同时充当两个数。哪怕 target 刚好等于 2 倍的某个元素按照题意也不应该返回它自己。所以当 left 和 right 相遇时必须终止。第二cur target 时为什么 left 1因为数组升序left 右移后 nums[left] 变大总和才有机会接近 target。同理cur target 时 right - 1。第三这里有一个很多人忽略的点这个解法只适用于有序数组。如果数组无序双指针直接失效你应该考虑哈希表。什么叫“失效”不是跑不出结果而是你无法在移动指针时“确信地排除无解区域”——数组无序时left 右移后 nums[left] 可能变小也可能变大你无法判断哪个方向更接近 target两个指针就不知道往哪走了。这个“有序是前提”的认知比背代码重要一百倍。再看三数之和。给定无序数组 nums找出所有不重复的三元组满足三数之和为 0。我直接给代码然后讲两个关键点def three_sum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 target -nums[i] while left right: cur nums[left] nums[right] if cur target: 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 cur target: left 1 else: right - 1 return res关键点一是排序。三数之和的基础是两数之和但题目给的是无序数组所以第一件事是排成有序排完之后内层循环本质上就是“固定 i对 i 右侧的子数组做对撞双指针”。关键点二是去重。去重的核心原则是“同一层循环内重复值只处理一次”。外层循环里如果 nums[i] 和上一个 nums[i-1] 相同说明以这个数为首的三元组已经在上轮找过了直接 continue。内层循环里找到一组答案后要循环跳过所有和当前 left 值相同的 left以及所有和当前 right 值相同的 right。这里有一个我踩过的坑在 append 之后如果只 left 1漏掉 while 跳过下一轮很可能得到完全相同的三元组然后你还得去重与其最后塞个 set 再转 list不如在找到答案的一瞬间就地“去重”。原地去重的思路是让 left 和 right 在移动后仍然位于一个“过去没处理过”的位置上这也是循环不变量的一个应用。3.2 快慢指针环形链表检测与链表中点定位链表里的双指针形态和数组不太一样数组下标有界链表节点是引用链。快慢指针最常见的使用场景是检测环代码很短但背后的证明很有味道。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为什么快指针每次走两步慢指针走一步有环就一定会相遇直观解释是进入环之后快指针相对于慢指针每一轮会多走一步相当于慢指针静止时快指针以每秒 1 步的速度追赶环是有限的所以必然追到。不存在“快指针刚好跳过慢指针”这种担心因为相对步长是 1不可能跨越一个节点却测不到碰撞——如果它们在某一步重合我们检查的就是那个重合点。如果你需要进一步找环的入口还有一个重要的结论在快慢指针首次相遇的点从该点出发一个指针从头节点出发另一个指针两者都以步长 1 前进下一次相遇点就是环入口。这个结论很多题解直接甩出来我建议你一定要自己推导一遍设头节点到环入口的距离为 a入口到相遇点的距离为 b相遇点距入口的剩余弧长为 c则环周长 L b c。慢指针走了 a b快指针走了 a b kL又因为快指针步数是慢指针的 2 倍有 2(ab) abkL得到 ab kL。也就是说从头出发走到相遇点刚好是 k 圈。那么从头节点和相遇点同时出发每走一步距离环入口各缩短 1必然在入口重合。这个推导我每次给别人讲的时候都会亲手画一遍比背公式牢固得多。链表中点的定位也依赖快慢指针快指针走两步慢指针走一步快指针到链表尾时慢指针恰好在中间。这个写法要留意链表节点数量的奇偶性。如果题目要求偶数长度时返回后一个中点while 条件要写成 fast and fast.next如果要求返回前一个中点条件要改成 fast.next and fast.next.next。细节差一个 next结果就差一个节点笔试时很容易被这种坑绊住。快慢指针在处理链表时还有一种应用场景找倒数第 k 个节点。让快指针先走 k 步然后快慢指针同步走快指针到末尾时慢指针恰好指向倒数第 k 个节点。这里同理先走的边界判断要仔细否则 k 等于链表长度时容易走出 None。3.3 同向快慢指针原地去重与移动零同向双指针是数组题里非常实用的一类它维护的核心是“两个指针把数组划分成已处理区、扫描区、待探索区”。这类题往往要求原地修改不开新的数组所以空间复杂度能压到 O(1)这是它比“新建列表再过滤”高明的地方。先看“移动零”。给定数组 nums把所有的 0 移到末尾同时保持非零元素的相对顺序并且必须在原数组上操作。def move_zeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1 return nums这个实现的思路是slow 指向“下一个非零元素应该放置的位置”fast 负责遍历。每遇到一个非零元素就把这个元素和 slow 位置的元素交换然后 slow 前进。交换而不是覆盖可以避免把尚未处理到的元素弄丢这是我在实战中反复强调的细节。如果你用“覆盖再补零”的做法也就是把非零元素往前挪、最后统一补零也行但要注意覆盖时别把后续还没扫描到的非零元素覆盖没了。再看“去除有序数组中的重复项”。给定一个升序数组原地删除重复元素返回新长度。这里同样用同向快慢指针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 1slow 维护的是“去重后的数组最后一个元素的位置”fast 是探索者。每当 fast 发现一个新值就把它接到 slow 后面并推进 slow。因为输入有序新值一定和之前不同所以不需要再额外判断“中间有没有重复值”。如果题目改成无序数组这个方法就不成立在移动 fast 前你得先确认这个值是否已经出现过那就不得不引入哈希表复杂度会跟着变。这一节的方法在我看来是双指针法里最容易被低估的。因为它没有“对撞”那么华丽的收敛过程也没有“快慢追环”那么巧妙的数学结论但它极其实用。你在很多字符串压缩、日志清理、数据清洗脚本里都能用同一套思路写出短路且高效的原地算法。3.4 滑动窗口无重复字符的最长子串与最小覆盖子串滑动窗口是双指针法中最灵活、也最容易写错的一类。它的要点不是“两个指针怎么动”而是“窗口内状态怎么维护”。窗口本身由 left 和 right 两个下标界定区间 [left, right] 内的元素构成当前正在处理的子串或子数组。right 负责扩展窗口left 负责收缩窗口两者只能同向移动。先看最经典的“无重复字符的最长子串”。给定一个字符串找出不含重复字符的最长子串的长度。def length_of_longest_substring(s): last_pos {} left 0 max_len 0 for right, ch in enumerate(s): if ch in last_pos and last_pos[ch] left: left last_pos[ch] 1 last_pos[ch] right max_len max(max_len, right - left 1) return max_len这段代码里有一个我认为最关键的细节last_pos[ch] left这个条件。如果不加这个判断直接写成if ch in last_pos那么 left 可能会回退。举个例子字符串是 “abba”当 right 指向最后一个 a 时a 上次出现的位置是 0但此时 left 已经在 2 的位置如果直接把 left 更新为 last_pos[a]1即 1窗口就会回退到包含重复 a 的状态结果错误。正确做法是只有当“上次出现位置仍在当前窗口内”时才更新 left。这个条件几乎是滑动窗口正确性的生命线。再看一个进阶题目“最小覆盖子串”。给定字符串 s 和 t在 s 中找到包含 t 所有字符的最短子串。这时窗口内不能用裸的 set 判断得用计数数组或字典维护“还缺哪些字符”。def min_window(s, t): from collections import Counter need Counter(t) miss len(t) left 0 start 0 min_len float(inf) for right, ch in enumerate(s): if need[ch] 0: miss - 1 need[ch] - 1 while miss 0: if right - left 1 min_len: min_len right - left 1 start left left_char s[left] need[left_char] 1 if need[left_char] 0: miss 1 left 1 return s[start:start min_len] if min_len ! float(inf) else 这个代码最开始可能不容易看懂我拆解开说。第一need 字典记录的是“t 中各字符还缺多少个”。初始为正表示缺当某个字符出现得比 t 需要的还多时need 会变成负数表示富余。miss 变量记录总共缺多少个字符只有 miss 归零才说明窗口已经覆盖 t。第二right 每扩展一步就把对应字符在 need 中减 1。如果该字符的 need 原来大于 0说明这个字符是“真正缺的”miss 也减 1如果 need 已经小于等于 0说明这个字符是富余的miss 不变。这里需要理解“正缺和富余的边界”need[ch] 0 的语义是“当前窗口内 ch 还不够 t 所需的数量”。第三left 收缩时做的是逆操作把 left_char 从窗口里移出去对应 need 加 1。如果加完以后 need[left_char] 0说明被移出去的字符恰好是“必需的”窗口又缺了这个字符miss 加 1于是退出 while让 right 继续扩张。这个过程本质上是一台精密的“供需机器”。每个字符在窗口进进出出need 字典就是供需差额miss 是总缺口数。把状态量定义清楚以后滑动窗口题就转化为两个循环的机械操作右指针负责供左指针负责求条件不满足时右扩条件满足时尝试左缩并更新答案。滑动窗口还有一个很多新手没意识到的好处它天然适合需要“连续”约束的问题。因为窗口本身就是一个连续区间任何需要保持连续性的子数组、子串问题用窗口来枚举候选区间都比暴力枚举要省去大量重复计算。关键是你得维护好窗口内的“聚合状态”不管是字符计数、区间和、还是最大值最小值都可以通过额外数据结构随窗口更新。4. 常见问题与排查技巧实录4.1 死循环、越界、丢解一张速查表帮你定位双指针代码的 bug 模式十分集中我整理了这几年debug碰到的高频问题按现象、原因、处理方式列成表格方便你对着检查现象常见原因排查方向程序卡住不退出指针移动条件写反死循环打印每个 while 轮次中 left、right 的值看是否符合“每轮必有一指针移动”数组越界循环边界用了 left right导致指针跑过头检查循环条件是否与题目“能否共用一个元素”匹配漏掉一组答案答案更新时机不对或收缩条件过紧回顾循环不变量确认每次更新答案时窗口/区间是否仍满足题目要求结果重复没做去重或去重位置不对检查外层每次固定值是否重复内层找到答案后是否跳过相等值left 回退滑动窗口的 last_pos 判断没有加 left确认“上次出现位置是否在当前窗口内”链表快指针报 Nonewhile 条件没检查 fast.next链表题务必先判 fast 和 fast.next 是否为 None这张表不全面但覆盖了我在刷题时遇到的绝大多数情况。你如果卡住了先对着表做一轮“体检”通常比从头翻题解更快。4.2 三条经验调试方法论、复杂度核对、与哈希表的选择第一条经验双指针题写完后务必在脑海里跑三个小用例再提交最小规模、常规规模、特殊边界。最小规模比如数组长度是 1 或 2链表只有一个节点常规规模取中间值特殊边界包括全是重复值、全是 0、全部相等、最长子串在末尾等等。我见过太多提交后才发现 left 越界的惨案都是因为只测了题目给的样例。用纸笔手动模拟三个用例也许要花五分钟但能够救回无数次罚时。第二条经验写完后要习惯性核对复杂度。双指针法的复杂度通常是 O(n)同向/快慢或 O(n log n)排序后对撞如果你发现自己写的版本是 O(n²)那大概率说明你没有真正利用好“每次排除一片区域”这个性质。比如三数之和外层固定 i 一次内层双指针从两端向中间扫描一次所以总复杂度是 O(n²)。这不是双指针失效而是问题的解空间本身就是二维的双指针把内层复杂度从 O(n) 的朴素枚举降到 O(n)整体仍然是 O(n²)。看清这一点你才不会被“怎么三数之和还是 n²”这个问题迷惑。第三条经验遇到双指针题先想能不能用双指针再想能不能用哈希表。实际工作中哈希表虽然写起来简单但它在空间复杂度上是 O(n)双指针通常可以做到 O(1)。比如有序数组两数之和哈希表可以做但空间多花一份双指针则省掉这份开销。而在“找是否存在某两个元素”这类问题时如果数组无序且无法排序比如对原始顺序敏感哈希表反而是更稳妥的选择。不要神化双指针它是工具不是信仰。另外一个我特别想分享的细节是排查双指针题时要习惯“把指针语义写在注释里”。我见过无数人写 left 或 right-- 完全不做解释自己隔天回看都忘了这个移动的依据。如果你在每处移动前都写一句“因为当前区间右端已不可能作为答案左端”调试时你就能快速判断这只移动是不是合理。这个习惯帮我省掉大量 debug 时间强烈建议你也试试。最后补一个我在实战中验证过的练习顺序如果你想把双指针法彻底吃透我给一套由浅入深的刷题顺序先从“两数之和II - 输入有序数组”入手建立对撞指针的基本手感然后做“三数之和”理解固定一层 内层双指针的组合再换到“盛最多水的容器”体会“移动高度较小的那一端”的贪心逻辑链表部分先做“环形链表”再做“链表中点”和“删除链表的倒数第N个节点”紧接着做“移动零”和“去除有序数组中的重复项”巩固同向双指针最后挑战“无重复字符的最长子串”和“最小覆盖子串”把滑动窗口的状态维护练扎实。按照这个顺序每一题都是前一题的微小变体难度递增不会让你有陡峭感。我个人在实际操作中发现学双指针法最忌讳的是“只看题解不写代码”。这类题的代码量通常很短短到你会产生一种“我已经会了”的错觉但只要合上答案自己写一遍就会在边界条件上翻车。哪怕只是把上面这几段示例代码亲手敲一遍再自己修改几个参数跑一遍用例收获也会远超看十篇题解。刷题没有捷径但把常见模式和常见坑位总结成文的经验可以帮你少踩一些我当年踩过的坑。接下来你自己动手试试吧把三个形态各写熟一道题后面再遇到任何双指针问题都不会慌。