好几年前我面试遇到一道题给一个升序排列的数组找出两个数使它们的和等于目标值。当时我提笔就写了两层 for 循环的暴力解面试官问我数组有序这个条件你一点没用上吗。后来他提示我用两个指针一头一尾往中间扫我才第一次体会到双指针算法的强大——同样的功能复杂度从 O(n^2) 直接降到 O(n)。事后回想这道题其实一点都不难真正难的是我从没意识到有序本身就是可以被利用的信息。双指针算法之所以让人觉得会了很简单、不会就抓瞎大致也是因为这个原因——它本质上是把暴力枚举时那些明显不可能的组合提前剪掉。双指针算法是一种非常基础又极其能打的编程思想。它不依赖复杂的数据结构核心就是用两个变量在数组里叫下标在链表里叫节点引用分别指向不同的位置通过有策略地移动这两个指针让原本需要两层循环才能解决的问题变成一层循环就能解决。很多 O(n^2) 的暴力题用双指针可以干净利落地降到 O(n)不少链表问题不用双指针基本没法高效处理。这篇文章我会从原理到代码从数组到链表把双指针的三个主要流派左右对撞、快慢指针、滑动窗口一次性讲透。每部分都给可以直接跑的代码再补一些我自己实际写题和做项目时踩过的坑。适合准备面试的、刷 LeetCode 的、以及工作中想优化一下代码的同学参考。1. 双指针不是一种算法而是一套省时间的思维模式很多初学者把双指针当成一种需要背模板的题型其实它完全不是某种独立的数据结构或算法它更像是一种使用信息的思维方式。理解这一点比背十个模板都重要。1.1 暴力解法的瓶颈在哪里我们还是拿开头的有序数组两数之和来说。暴力做法长这样固定第一个数然后遍历它后面的所有数看哪个跟它加起来等于 target。两层循环时间复杂度 O(n^2)。如果数组有十万个数最坏情况下要比较五十亿次在性能要求稍高的环境里基本就崩了。问题出在哪暴力解法把每一对组合都检查了一遍根本没有利用数组有序这个信息。举个例子数组是 [1, 3, 5, 7, 9, 11]目标是 10。暴力解会逐一检查 13、15、17……然后再检查 35、37……里面绝大多数组合一眼就能看出大于 10 或者小于 10但程序还是在傻傻地算。如果让两个下标分别从数组的两头出发情况就会完全不同。左指针指到 1右指针指到 1111112 大于 10那说明1 加右边任何一个数都不可能等于 10吗这里有个关键推理因为数组有序右指针向左移动和会变小。当 111 已经大于 target 时左指针右边的所有数只会更大因此唯一可行的方向是右指针左移。这样一步就排除了一整批不可能的组合效率自然高得多。1.2 双指针为什么能省时间双指针省时间的本质不是少写了一层循环这么简单而是每一步移动都有信息量。每次移动指针你其实是在说一句话以这个指针当前位置为基准的某些组合已经不可能是答案了不用再看了。还是刚才的例子left 在 1right 在 11和是 12 大于 10于是 right 左移到 9。这个动作的意思是1 和 11、以及任何大于 11 的数这里没有的组合全部被排除。再看 1910刚好命中。整个搜索过程中left 和 right 各自只会向中间移动最坏情况下两个指针合计移动 n 步所以整体是 O(n)。这个每一步移动排除一批解的思路就是双指针算法的灵魂。1.3 双指针的三个流派各管什么我把双指针分成三个流派每个流派都有自己擅长的场景一开始确定好类型思路会清晰很多。左右对撞指针两个指针一个在头、一个在尾相向而行。典型场景是有序数组两数之和反转数组回文串判断三数之和。快慢指针两个指针同方向走但速度不同典型场景是链表判环寻找链表中点寻找倒数第 N 个节点。滑动窗口两个指针同向移动一左一右夹出一个连续区间典型场景是最长无重复子串最小覆盖子串长度最小的子数组。后面几节我就按这三个流派一个个拆开讲。2. 快慢指针链表里奔跑的两个影子在所有双指针变体中快慢指针在链表题里几乎是无可替代的。因为它不需要额外开数组存节点也不需要知道链表长度就能解决很多走一步看一步的问题。2.1 Floyd 判圈算法为什么快指针走两步最稳判断一个链表有没有环最经典的做法就是快慢指针。慢指针每次走一步快指针每次走两步。如果链表有环快指针最终会在环里从后面追上慢指针就像环形跑道上速度快的人迟早会套圈追上速度慢的人。如果链表没有环快指针会先走到链表尾部碰到 null 结束。为什么快指针要走两步而不是三步、四步关键在于相对速度。快指针每步走 2慢指针每步走 1那么每轮循环里快指针相对慢指针前进 1 步。这意味着追上的过程是一个一个节点慢慢逼近的永远不会从慢指针头上直接跳过去所以只要环存在两者一定会在环内相遇。如果快指针每步走 3相对速度是 2就有可能在两个节点之间反复横跳理论上存在永远错过的情况。虽然实际链表里大多数情况也能碰到但两步是最简单、最好证明的选择。def has_cycle(head): if not head or not head.next: return False slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False这里有个特别容易忽略的细节循环条件必须是 fast and fast.next不能只写 fast。因为快指针一次走两步如果 fast.next 是 None那么 fast.next.next 就是直接操作 None 的属性会抛异常。这个坑我见太多人踩过了包括早期的我自己。2.2 找到环的入口一次巧妙的数学推导知道有没有环还不够有些题还会要求找到环的入口节点。做法是先让快慢指针在环里相遇然后让一个指针从链表头部重新出发另一个指针从相遇点出发两者都每次走一步它们再次相遇的位置就是环的入口。这个结论第一次见的人会觉得像魔法其实推导很简单。设链表头部到环入口的距离为 a环入口到相遇点的距离为 b相遇点继续走到环入口的距离为 c。慢指针走了 ab 步快指针走了 abcb a2bc 步。因为快指针走过的路程是慢指针的两倍所以2(ab) a2bc两边化简得到 a c。也就是说从链表头走 a 步到达环入口和从相遇点继续走 c 步到达环入口的距离是一样的。于是让两个指针以相同速度分别从这两处出发第一次碰头就一定是在环入口。def detect_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: p head while p is not slow: p p.next slow slow.next return p return None2.3 快慢指针的另外两个高频应用除了判环快慢指针在链表题里还有两个高频率的用法。第一个是找链表中点。慢指针走一步快指针走两步等快指针走到链表末尾时慢指针刚好停在中间位置。这个操作在很多题目里是前置步骤比如回文链表就是先找到中点再把后半段链表反转然后和前半段对比。需要注意节点数是奇数还是偶数奇数时慢指针正好落在中间节点偶数时慢指针会落在前半段的最后一个节点具体实现时要根据题目要求调整。第二个是删除倒数第 N 个节点。先让快指针提前走 N 步然后快慢指针一起走等快指针到底时慢指针正好在倒数第 N 个节点的前一个位置趁机把那个节点摘掉就行。不过有个边界要注意如果快指针提前走 N 步后已经变成 None说明要删除的是头节点这种情况需要单独处理。def remove_nth_from_end(head, n): dummy ListNode(0, head) fast slow dummy for _ in range(n): fast fast.next while fast and fast.next: fast fast.next slow slow.next slow.next slow.next.next return dummy.next设置 dummy 哨兵节点是这类删除题的标准操作可以避免处理删除头节点的特例。3. 左右对撞指针有序数据的两头夹击左右对撞指针应该是双指针里最容易理解的一种。在数组、字符串这类连续存储的结构上两个指针一个从开头往右一个从结尾往左像两个人在排队的人群里两头往中间找目标一样。它的核心前提是数据的有序性或者某种递推关系否则你没法根据当前两个位置的比较结果来决定该移动哪一边。3.1 有序数组两数之和最基础的对撞模型题目背景一个升序排列的整数数组找到两个数使和为 target返回下标。头尾各放一个指针计算当前和如果等于 target 就返回如果小于 target说明需要更大的数左指针右移如果大于 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 而不是 left right。因为我们要找的是两个不同位置的数如果让 left 走到和 right 重合那个位置上的数会被用两次不符合要求也通常没有意义。这个细节在面试里很常被追问。3.2 三数之和排序 对撞 去重三数之和是两数之和的进阶版在数组中找到所有不重复的三元组使三个数之和为 0。思路是先把数组排序然后固定一个数剩下的两个数用左右对撞指针去找。排序是为了让对撞指针成立也是去重能实现的前提。def three_sum(nums): nums.sort() n len(nums) res [] for i in range(n - 2): if nums[i] 0: break if i 0 and nums[i] nums[i - 1]: continue 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这段代码里有三个去重点任何一个处理不好都会出重复答案。第一外层循环固定的数如果和前一个相同就跳过第二找到一组答案后左指针要跳过所有重复元素第三右指针同样要跳过重复元素。面试时很多人能想到双指针但去重考虑不全结果一堆重复三元组反而暴露了细节功底。3.3 反转数组与回文判断对撞指针的小甜点反转数组和回文判断是对撞指针最简单、最直观的应用。反转数组左右指针分别指向首尾交换两个位置的元素然后左指针右移、右指针左移直到相遇。整个过程只遍历了一半的元素时间复杂度 O(n/2) O(n)空间复杂度 O(1)。回文判断稍微变一下左右指针从两端往中间走每次比较两个字符是否相同只要有一次不同就直接返回 False否则继续往中间靠。这个思路还可以扩展到不区分大小写、忽略空格等场景只需要在移动指针前先做字符过滤。def is_palindrome(s: str) - bool: left, right 0, len(s) - 1 while left right: if s[left].lower() ! s[right].lower(): return False left 1 right - 1 return True这类题的边界条件相对简单但适合用来训练先想清楚指针移动条件再写代码的习惯。4. 滑动窗口维护一段连续的好区间滑动窗口可以看作是双指针里最灵活、也最容易写错的一个流派。两个指针从左往右同向移动它们之间的区间就是一个窗口。每次右指针向右扩展窗口当窗口不再满足条件时左指针向右收缩窗口。整个过程就像在文本编辑器里拖动一个选区右边往前扩展左边跟着回收窗口的大小并不是固定的。4.1 最长无重复子串从暴力到滑窗的完整推导题目给定一个字符串找出其中不含有重复字符的最长子串的长度。暴力做法是枚举所有子串然后对每个子串检查有没有重复字符O(n^3) 甚至更差。用滑动窗口可以把复杂度降到 O(n)。具体做法是右指针不断右移把新字符加入窗口如果发现字符已经存在说明窗口现在不合法于是左指针不断右移直到这个重复字符被移出窗口每轮都记录当前窗口的长度。这里我用了一个集合来保存窗口内的字符。def length_of_longest_substring(s: str) - int: seen set() left 0 ans 0 for right, ch in enumerate(s): while ch in seen: seen.remove(s[left]) left 1 seen.add(ch) ans max(ans, right - left 1) return ans这段代码的正确性来自一个事实当右指针走到某个位置时左指针只会向右移动不会回退。因此所有字符最多被加入一次、移除一次每个右指针位置下的窗口都是以当前右指针为右边界的、最长的合法窗口。这个单调性是滑动窗口能高效工作的根本原因。一个常见的优化是如果重复的不只是字符而是更复杂的条件不满足的情况可以改用哈希表记录每个字符最后一次出现的位置这样左指针可以一下子跳到重复字符的后一个位置而不需要一步一步挪。但作为入门先用 while 循环逐步收缩是最不容易出错的。4.2 最小覆盖子串滑动窗口的经典难题最长无重复子串是窗口不合法就收缩的典型而最小覆盖子串则是先扩张到合法再收缩求最小的典型。题目要求在字符串 s 中找出包含字符串 t 中所有字符的最短子串。做法分两步。第一步右指针不断右移直到窗口里包含了 t 中所有需要的字符第二步左指针不断右移在保持窗口仍然覆盖所有字符的前提下尽量缩短窗口每缩短一步就更新答案。然后右指针继续右移重复扩张—收缩循环。from collections import Counter def min_window(s: str, t: str) - str: need Counter(t) missing len(t) left 0 ans for right, ch in enumerate(s): if need[ch] 0: missing - 1 need[ch] - 1 while missing 0: if not ans or right - left 1 len(ans): ans s[left:right 1] left_ch s[left] need[left_ch] 1 if need[left_ch] 0: missing 1 left 1 return ans这里用 missing 变量记录还没有被满足的字符个数而不是每轮都重新统计整个窗口这是个非常关键的优化。如果窗口里某个字符出现次数比需要的多它的 need 值会变成负数但这不影响 missing 的判断因为 missing 只有在 need 从 0 变正时才增加从正数变 0 时才减少。4.3 滑动窗口的通用模板与三道经典题滑动窗口题目千变万化但代码骨架其实可以总结成一个模板left 0 counter {} # 视题目需要改用 set、dict、int 等 for right in range(n): # 1. 扩展窗口把 s[right] 加入窗口状态 add(right) # 2. 收缩窗口当窗口不再满足条件时 while not valid(): remove(left) left 1 # 3. 更新答案根据题目要求记录结果 update(right - left 1)这个模板最需要想清楚的是三件事以什么数据结构维护窗口状态、窗口合法怎么定义、答案是在收缩前更新还是收缩后更新。这三件事的答案不同就是不同题目的差异所在。下面三道题建议按顺序刷因为它们代表了三种不同的窗口管理方式长度最小的子数组窗口和大于等于 target 时收缩答案在收缩时更新。最长无重复子串窗口出现重复字符时收缩答案在收缩后更新。最小覆盖子串窗口覆盖所有字符时收缩答案在收缩过程中更新。把这三道题吃透滑动窗口基本就过关了。5. 边界条件、踩坑清单与多语言实现对比双指针代码看着短但真正写起来翻车点非常多。这一节我把自己实际写题和帮别人 review 代码时遇到的高频问题集中整理一下全部是真实踩过的坑。5.1 最常见的五个边界问题第一忘记移动指针导致死循环。最典型的是在 while 循环里判断完条件后忘了 left 1 或 right - 1结果循环永远出不来。尤其是写三数之和这类逻辑分支较多的代码时每个分支都要注意指针是否移动了。第二循环条件误用 。找两数之和时用 left right会导致同一个位置的数被计算两次。在大多数找两个不同位置元素的题目里left right 才是对的但在二分查找这类题里left right 又是对的。判断标准不是死记硬背而是想清楚指针相遇时那个元素还有没有被处理的必要。第三链表题没有判空。快慢指针判环时如果传入空链表直接访问 head.next 就会抛异常。统一做法是开头先检查 if not head or not head.next。类似地快指针每次走两步时循环条件要写 fast and fast.next保证不会出现访问 None.next的情况。第四去重时越界。三数之和里跳过重复元素的 while 循环经常写成 while nums[left] nums[left1]但没有加 left right 的边界条件导致 left 一路滑出数组边界。正确写法是在 while 条件里一并写上 left right。第五返回值的选择。很多题目要求返回下标、返回数值、返回子串本身不同题目对找不到答案时返回什么的定义不一样。写代码前先确认清楚避免返回类型混乱。5.2 多语言实现双指针时要注意什么双指针本身不涉及高深语法但不同语言写起来的坑位不太一样。我用一张表总结一下语言主要注意点Python字符串不可变子串截取是 O(n) 拷贝频繁截取要注意性能列表切片也是 O(n)建议优先用下标表示区间Cvector 的 size() 返回无符号数和负数比较时要小心链表题注意指针判空用下标访问前一定要确认不越界JavaHashSet/HashMap 声明泛型要写全Integer 对象比较值用 equals 而不是 否则 128 以上的数会踩缓存坑补充两个多语言示例。C 版的有序数组两数之和和 Python 版思路完全一致// C 版本有序数组两数之和 vectorint twoSum(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) return {left, right}; else if (sum target) left; else right--; } return {-1, -1}; }Java 版的链表判环注意判空条件// Java 版本链表判环 public boolean hasCycle(ListNode head) { if (head null || head.next null) return false; ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) return true; } return false; }5.3 复杂度的正确分析姿势很多人写题会说双指针是 O(n)但要能解释清楚为什么。关键是每个指针在最坏情况下只会从一端移动到另一端一次不会回头。以两数之和为例left 最多右移 n 次right 最多左移 n 次合计不超过 2n 次操作所以是 O(n)。滑动窗口同理right 和 left 各自最多移动 n 次总操作 O(n)。三数之和外层要遍历 n 个数内层双指针最多移动 n 次整体 O(n^2)加上排序 O(n log n)总复杂度 O(n^2)。6. 双指针思维的生活应用与技术迁移写到这里有读者可能会问双指针不就是刷题用的吗实际工作中到底用不用得上说实话直接用双指针这个名字的场景确实不多但它背后的思维模式——用两个参照物不断逼近目标、减少无效搜索——在很多领域都能看到影子。6.1 生活中的双指针现象我自己喜欢用三个生活场景来向朋友解释三种指针。左右对撞指针就像两个工作人员从长队的两头往中间核对名单两个人手里的名单是同一个有序列表哪头对不上就移动哪头很快就能锁定目标位置。快慢指针就像环形跑道上的两名运动员跑得快的人如果速度刚好是慢的人两倍他一定会在某个时刻从后面套圈追上慢的人跑圈的人看到这个现象从来不会觉得奇怪但代码里这就是判环的依据。滑动窗口则像一扇沿着一排展示框滑动的陈列窗窗子左边的边界决定起点右边的边界决定终点你能看到的永远是连续的一段想看下一段就同时移动左右边框。这几个类比不是严格的数学对应但用来帮助初学阶段建立画面感非常好使。6.2 双指针思维在文本、图像与自动化场景中的影子在真实工程里用两个游标/参照物去逼近目标的思路远比想象中常见。文本和文档处理是最直观的领域。编辑器的选区本质就是两个光标位置一个起点一个终点移动其中一个就改变了选中区间版本管理系统里的 diff 算法本质上也是在两个文本序列上做类似双指针的比较找出新增和删除的行。很多文档处理工具里查找连续片段合并两个有序列表检查括号匹配这类功能底层都有双指针的影子。图像处理里也有类似思想比如扫描线算法通过一根扫描线在图像上移动逐个像素判断边界边缘检测中经常需要从图像两端的初始位置向内逼近找到真正的目标区域边界。我在做 OCR 工具的本地部署时处理文本框的合并与排序就用到了同时维护两个边界位置、通过比较相邻框的位置关系决定是否合并的思路这和双指针判断当前元素是否要继续扩展窗口如出一辙。工业自动化场景同样能见到。超声波测氧浓度时设备需要在一段连续采集的数据里找一个稳定的浓度区间处理逻辑很像滑动窗口窗口逐渐扩大收集样本一旦发现波动超出阈值就收缩窗口重新积累。包括某些控制算法里的二次开发当需要实时判断两个传感器读数是否收敛到一个阈值范围内时两个端点不断向中间逼近的框架也非常实用。这些场景不会直接说这是双指针但理解了双指针的人遇到这类问题时往往会很快想到可以用两个游标配合循环来解这就是思维能力迁移的价值。6.3 学习建议不要背模板要理解排除二字最后分享一个我自己的学习建议。初学双指针时不建议先背模板建议在纸上手动模拟一遍指针的移动过程。拿出一个测试用例一步一步画出 left 和 right 的位置变化每移动一步就在旁边写下这一步排除了哪些不可能的组合。等你画过三五道题之后会发现双指针的代码就是移动—判断—再移动的循环根本不需要死记硬背。我到现在写双指针相关的题仍然会先在草稿纸上画数组下标尤其是三数之和、最小覆盖子串这种逻辑比较厚的题画一遍比 debug 半天有用得多。这个习惯一直保留到了工作里写复杂循环前先画指针走向能省下大量调试时间。双指针值得每个写代码的人都花点时间弄懂它把暴力搜索变成有方向感的探索是很多人第一次感觉到算法思维和写业务代码之间的微妙差别的地方。学会它之后再看很多 O(n^2) 的代码你会有一种条件反射式的直觉这里是不是能用两个指针优化一下这种直觉一旦建立起来你写任何循环代码之前都会多想一步这层循环能不能用双指针干掉对代码质量的提升立竿见影。
