很多人刚开始刷算法题的时候最容易遇到的一个情况是明明题目意思看懂了暴力解法也能写出来但一提交就是超时一看题解发现别人用几行代码就把复杂度从 O(n²) 降到了 O(n)思路还特别清晰。这个别人用的很多时候就是双指针。双指针不是某种高级数据结构的专属玩法它本质上是一种遍历策略的优化在单个数组或链表上通过维护两个指针下标或节点来协同完成遍历避免不必要的重复扫描。我最早接触它是在做有序数组两数之和那道题的时候当时用嵌套循环老老实实跑数据量一大直接暴毙后来学会了左右对撞指针几行代码就把时间复杂度拉到了线性级别那种原来还能这么玩的感觉确实让人对算法这件事开了窍。这篇文章我会从双指针的核心思想讲起把最常见的三类玩法——对撞指针、快慢指针、滑动窗口——逐个拆开配合完整代码、复杂度分析和实战经验讲清楚什么时候该用双指针、为什么用双指针能快、用的时候有哪些坑要躲。无论你是刚开始刷题的新手还是想系统梳理技巧准备面试的进阶选手这篇都值得认真过一遍。1. 双指针的本质与三大主流场景想用好双指针第一步不是背模板而是理解它到底在优化什么。一个普通的单层循环时间复杂度是 O(n)遇到需要两两组合、子数组统计这类问题新手第一反应往往是嵌套循环复杂度直接变成 O(n²)。双指针的核心价值就是利用数据本身的规律砍掉那些不可能产生答案的无效比较让两个指针各走各的总移动次数不超过 O(n)。那什么样的数据有这种规律常见的有三类有序性数组排好序后指针移动的方向可以明确决定下一步该往哪边走这是对撞指针的基础。相对位置与步长差在链表这类结构里两个指针以不同速度前进能产生追上、相遇、刚好落位等效果这是快慢指针的玩法。连续区间一个指针固定窗口左端另一个指针扩展窗口右端能在移动中维护窗口的某种统计信息这是滑动窗口的核心思路。我个人习惯把这三类场景整理成一张对照表做题时先判断题目属于哪一类再套对应的框架双指针类型移动方式典型数据结构时间开销适用问题特征对撞指针两端向中间移动有序数组、字符串O(n)两数之和、回文判断、容器装水快慢指针同向不同速移动链表、数组在环内O(n)环检测、环入口、中间节点滑动窗口同向移动维护区间数组、字符串O(n)每个元素最多进出窗口一次最长/最短子串、窗口统计注意一个重要的前提双指针并不是所有题目都能用。它要求数据有足够的结构信息或者问题本身可以转化为由两个位置共同决定答案的形态。如果数据完全无序又需要穷举所有的两两组合那双指针也无能为力老老实实排序后再说。这一点在面试中非常关键因为面试官更看重的是你能不能判断出该用什么而不只是代码写得快。另一个值得提前说的点双指针的代码量通常很少但边界条件极其容易出错。左指针小于右指针还是小于等于右指针快慢指针判空时先判 fast 还是先判 fast.next滑动窗口收缩时统计信息怎么更新这些都是实战里反复踩的坑后面每个部分我都会给出具体的注意事项。2. 对撞指针一头一尾夹逼答案对撞指针是所有双指针里最直观、也最容易上手的形态。它先让左指针指向数组最左端右指针指向最右端再根据当前两个指针指向的元素之和或某个判断条件来决定是左指针向右移、右指针向左移还是得到答案直接收工。之所以能这样移动依赖的是数据的有序性或者可比较的单调性。举个例子一个升序数组左指针指着最小值方向右指针指着最大值方向。如果两个数的和已经大于目标值说明右指针这个数太大了只能往左挪找更小的数如果和小于目标值说明左指针这个数太小了往右挪找更大的数。每一步都排除了大量不可能的组合所以总的时间复杂度是 O(n)而不是暴力的 O(n²)。2.1 两数之和有序数组最经典的对撞演示题目背景很常见给定一个已按升序排列的整数数组和一个目标值 target要求找出两个数使得它们的和等于 target返回这两个数的下标。经典的暴力解法是两层循环枚举所有组合def two_sum_bruteforce(numbers, target): n len(numbers) for i in range(n): for j in range(i 1, n): if numbers[i] numbers[j] target: return [i 1, j 1] return []这个写法在数组长度几万的时候就开始吃力了时间复杂度 O(n²)。换用对撞指针代码长这样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] # 题目要求下标从1开始 elif current_sum target: # 和太小只能让左指针往右走变大一点 left 1 else: # 和太大只能让右指针往左走变小一点 right - 1 return []理解这段代码的关键在于为什么可以大胆移动指针。当 current_sum target 时说明 numbers[left] 和当前右指针指向的数相加都不够那么 numbers[left] 和右指针左边更小的数相加就更不可能够所以左指针左边的全部组合都不用再看了直接 left 1。同理当 current_sum target 时说明 numbers[right] 太大了右指针右边更大的数更不可能匹配所以 right - 1。每次移动都排除了一批组合整个过程 left 和 right 总共移动不超过 n 次时间复杂度就是 O(n)。这道题还经常变体成无序数组版本。无序时就不能直接对撞了要么先排序再对撞排序 O(n log n)要么用哈希表做一遍线性扫描O(n) 时间 O(n) 空间。选哪种取决于题目是否要求返回下标、以及是否允许修改原数组。如果要求返回原数组下标且不能排序哈希表是更合适的方案。2.2 三数之和固定一个再对撞两个两数之和学会后三数之和就是一个非常自然的扩展先排序然后固定第一个数剩下的两个数用对撞指针去找。看代码def three_sum(nums, target0): 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 target: result.append([nums[i], nums[left], nums[right]]) # 跳过重复的 left while left right and nums[left] nums[left 1]: left 1 # 跳过重复的 right while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif total target: left 1 else: right - 1 return result这里面有三个细节值得重点说。第一为什么先排序。三数之和要找的是元素本身而不是下标排序不会破坏答案却能让数组拥有单调性这是对撞指针能工作的前提。排序的 O(n log n) 开销远小于三层循环的 O(n³)所以整体是划算的。第二为什么固定元素要去重。假设数组里有多个相同的数作为第一个数如果不跳过会找出重复的三元组。比如 [-1, -1, 1, 0] 这类数据第一次 i0 时固定 -1已经把所有包含 -1 的组合找完了第二次 i1 还是 -1再找一遍必然重复。所以if i 0 and nums[i] nums[i - 1]这行是必须的。第三为什么找到答案后 left 和 right 也要跳过重复值。同样的道理找到一组后如果下一个 left 和当前值相同那么组合必然重复。跳过重复项之后再正常移动一步才能保证不遗漏、不重复。三数之和是面试高频题代码框架背熟不算本事能解释清楚每个去重逻辑为什么存在才是面试官想听到的。2.3 回文串判断与字符串对撞对撞指针不只用于求和问题在字符串处理里同样好用。经典题目验证回文串给定一个字符串只考虑字母和数字字符忽略大小写判断它是否为回文串。比如 A man, a plan, a canal: Panama 就是一个回文串。最直观的做法是先过滤掉非字母数字的字符再反转对比。但这样需要额外的空间来存储处理后的字符串。用对撞指针可以不构造新字符串在原串上直接判断def is_palindrome(s): left 0 right len(s) - 1 while left right: # 跳过非字母数字字符 while left right and not s[left].isalnum(): left 1 while left right and not s[right].isalnum(): right - 1 if s[left].lower() ! s[right].lower(): return False left 1 right - 1 return True这段代码里最容易写错的是内层 while 的边界判断。如果你写成while not s[left].isalnum(): left 1当字符串全是特殊字符时left 会一路越界直接抛异常。所以在内层循环里必须同时加上left right的条件防止指针走出字符串范围。这也是对撞指针通用的边界意识任何一次指针移动都要先想清楚它可能走到哪里去。从这两道题能看出一个规律对撞指针适合两个端点共同决定答案的问题。判断回文时头尾字符相等就继续往中间缩不相等就直接否定求和时两端之和与目标比较后决定移动方向。这类题的核心训练点就是你能不能从两端组合里提取出移动哪一端的决策规则。3. 快慢指针一快一慢妙用无穷快慢指针在对撞指针的基础上换了种思路两个指针从同一起点出发一个每次走两步快指针一个每次走一步慢指针。由于速度不同它们会在某些特定位置形成距离差这就能用来解决很多链表类的经典问题。我最初觉得快慢指针有点技巧性过强但用多了就发现它其实就是用相对速度制造一个可预测的位移关系。生活中的类比就是操场跑步两个人速度不同快的迟早会追上慢的如果跑道是环形的追上的那一刻就能证明这是一个环。3.1 环形链表检测为什么快指针一定能追上慢指针题目给定一个链表判断链表中是否有环。这里说的环是指链表中某个节点的 next 指针指向了之前出现过的节点导致后续遍历永远走不完。用快慢指针的解法非常简洁def has_cycle(head): slow head fast head while fast is not None and fast.next is not None: slow slow.next fast fast.next.next if slow is fast: return True return False为什么这个算法一定有效关键在相对速度。快指针每次比慢指针多走一步相当于追慢指针的速度是每步一格。如果链表无环快指针会先到达末尾循环正常结束如果链表有环快指针会进入环内不断绕圈最终一定会追上慢指针。有人会问会不会快指针直接跳过慢指针不会。因为在环内每次快指针相对慢指针只靠近一步不存在跳过去的可能。这段代码还有一个常见的边界坑while fast is not None and fast.next is not None这个判断顺序不能反也不能省略。如果 fast 本身是 None访问 fast.next 会报错如果 fast.next 是 None访问 fast.next.next 会报错。所以判空条件必须两步都查。3.2 环形链表 II不只是判断还要找入口判断完有没有环进阶题就是找出环的入口节点。解法是在快慢指针第一次相遇后把快指针重置到链表头部然后两个指针都改为每次走一步它们再次相遇的位置就是环的入口。def detect_cycle(head): slow head fast head while fast is not None and fast.next is not None: slow slow.next fast fast.next.next if slow is fast: # 找到相遇点重置 fast fast head while fast is not slow: fast fast.next slow slow.next return fast return None这个结论看着神奇用小学数学推一下就明白了。假设链表头到环入口的距离是 a环入口到相遇点的距离是 b相遇点再到环入口的距离是 c。环的长度就是 b c。慢指针走的路程是 a b快指针走的路程是 a b k(b c)其中 k 是快指针多绕的圈数。因为快指针速度是慢指针的 2 倍所以2(a b) a b k(b c)化简得a b k(b c)再看 a 和 c 的关系既然 a k(b c) - b (k - 1)(b c) c也就是说从链表头出发走 a 步等价于从相遇点走 c 步再多绕 k-1 圈。所以只要把快指针重置到头部两个指针同速前进它们就恰好会在环入口相遇。这个推导不需要背理解了以后遇到类似问题能很快类推。3.3 中间节点与倒数第 k 个节点快慢指针的另一个高频应用是找链表的中间节点。快指针走完时慢指针恰好停在中间def middle_node(head): slow head fast head while fast is not None and fast.next is not None: slow slow.next fast fast.next.next return slow这里注意当链表节点数为偶数时这种写法返回的是两个中间节点中的后一个。比如 [1,2,3,4]返回的是 3。如果你想要前一个需要在循环条件上做调整比如while fast.next is not None and fast.next.next is not None。具体用哪个取决于题目定义面试时最好主动跟面试官确认。找倒数第 k 个节点则是先让快指针走 k 步再同步前进的思路def kth_from_end(head, k): slow head fast head for _ in range(k): if fast is None: return None # k 大于链表长度 fast fast.next while fast is not None: slow slow.next fast fast.next return slow这个技巧能一次遍历完成不需要先求出链表长度再走 n-k 步。它的本质是让快慢指针之间保持 k 步的距离差快指针到末尾时慢指针自然就在倒数第 k 个位置。实现时要注意 k 的有效性判断如果快指针还没走完 k 步就遇到 None说明 k 超出了链表长度应该直接返回空。4. 滑动窗口区间的动态维护艺术滑动窗口严格来说也是双指针的一种只是两个指针都从同一端出发、同向移动它们围起来的区间像一个滑动的窗口。窗口左端用 left 维护右端用 right 扩展通过不断调整窗口大小来寻找满足条件的子数组或子串。它最擅长解决连续子序列 最值/计数类问题。滑动窗口的核心逻辑可以总结成一句话右指针负责扩张窗口左指针负责收缩窗口每次窗口满足条件时记录答案。因为每个元素最多被左指针和右指针各访问一次所以总时间复杂度是 O(n)比暴力枚举所有子数组/子串的 O(n²) 要快一个数量级。4.1 无重复字符的最长子串入门必会题目给定一个字符串 s找出其中不含有重复字符的最长子串的长度。比如 s abcabcbb答案是 3对应子串 abc。用滑动窗口的解法def length_of_longest_substring(s): window set() left 0 ans 0 for right, ch in enumerate(s): # 如果当前字符已经在窗口中收缩左边界直到没有重复 while ch in window: window.remove(s[left]) left 1 window.add(ch) ans max(ans, right - left 1) return ans理解这段代码要抓住窗口合法性这个概念。right 字符加进来之前窗口内是不能有重复字符的如果新字符已经在窗口里了就说明窗口不再合法需要不断从左边移除字符直到把与新字符相同的那个旧字符也移出去新字符才能安全加入。每加入一个合法字符后窗口长度 right - left 1 就可能是新的答案。这里有个细节值得提一下上面用 set 来记录窗口内字符删除时是从左往右删的所以删除的字符一定还在 set 里。但如果你在删除前没有判断该字符是否还在窗口内就可能会出现 KeyError。我在初学时就栽过这个跟头后来习惯了用哈希表字典来记录字符出现次数删除时计数减一为 0 才移除键这样更稳妥也更方便扩展到处理有重复字符的情况def length_of_longest_substring(s): from collections import defaultdict window defaultdict(int) left 0 ans 0 for right, ch in enumerate(s): window[ch] 1 while window[ch] 1: left_char s[left] window[left_char] - 1 if window[left_char] 0: del window[left_char] left 1 ans max(ans, right - left 1) return ans4.2 最小覆盖子串从最长到最短的思维转换无重复字符那道题是找最长滑动窗口还有一种常见变体是找最短。经典题是最小覆盖子串给定字符串 s 和 t在 s 中找出包含 t 所有字符包括重复字符的最短子串。这题的难点在于窗口的合法性不是无重复这么简单而是要统计 t 中每个字符是否都被覆盖。解法是用两个哈希表need 记录 t 中每个字符的需求量window 记录当前窗口中各字符的实际数量。再用一个变量 valid 记录已满足需求量的字符种类数当 valid 等于 need 的长度时说明当前窗口已经覆盖了 t 的全部字符。def min_window(s, t): from collections import Counter, defaultdict need Counter(t) window defaultdict(int) left 0 valid 0 start 0 min_len float(inf) for right, ch in enumerate(s): # 扩张窗口 if ch in need: window[ch] 1 if window[ch] need[ch]: valid 1 # 收缩窗口 while valid len(need): if right - left 1 min_len: min_len right - left 1 start left left_char s[left] if left_char in need: window[left_char] - 1 if window[left_char] need[left_char]: valid - 1 left 1 return s[start:start min_len] if min_len ! float(inf) else 这段代码我不建议死记硬背而是建议你把它当作一个模板来理解。它的骨架其实是统一的右指针每走一步更新窗口内的统计信息判断当前窗口是否满足题目条件如果满足尝试收缩左指针并在收缩过程中更新答案或最优值。最小覆盖子串这道题还透露了一个很重要的经验最长类问题通常在窗口合法时记录答案并扩张不合法时收缩最短类问题正好反过来在窗口合法时收缩并记录答案不合法时扩张。理解了这个方向遇到新的窗口类题目就不容易乱。4.3 窗口内最大值双指针与单调队列的组合滑动窗口还有一个进阶应用就是求每个固定大小窗口内的最大值或最小值。这道题表面看起来是滑动窗口 每次扫描窗口内元素 O(k)总体复杂度 O(nk)但如果用单调队列配合双指针可以做到 O(n)。思路是这样的维护一个从左到右单调递减的双端队列队列里存的是数组下标。窗口每次右移时先把新元素从队尾插入插入前把所有比它小的下标全部弹出因为它们不可能是之后窗口里的最大值再把队头已经离开窗口的下标弹出最后队头就是当前窗口的最大值。这个技巧在滑动窗口最大值这类题里是标配也是复习双指针时值得顺手掌握的配套工具。5. 双指针实战中的常见问题与避坑清单双指针代码量不大但边界条件极其密集。我在刷了几十道双指针题之后慢慢总结出一套自己的排查顺序遇到 bug 时按这个顺序检查往往能很快定位问题。5.1 循环边界left right 还是 left right这是对撞指针里最经典的困惑。拿二分查找和两数之和对比二分查找的区间内可能存在独立答案目标值在某个位置所以通常用left right因为当 left 和 right 指向同一个位置时这个位置也可能是答案而两数之和要求两个不同的数所以用left right因为 left right 时只有一个元素不可能构成两个数的组合。判断依据其实只有一条left 和 right 指向同一个位置时这个位置有没有可能是合法答案。如果不可能就用left right如果可能就用left right。5.2 指针越界先想清楚指针能走到哪在所有双指针题目中越界是最高频的 bug。对撞指针里内层跳过非法字符的 while 必须加上left right快慢指针里访问 fast.next 之前必须确认 fast 不为空滑动窗口里收缩窗口时要保证 left 不超过 right。这些细节单独看都很简单但写代码时大脑一旦顺利起来就会忽略所以我的习惯是每一处指针移动的代码旁边先问一句这里会不会越界。5.3 去重逻辑三数之和为什么容易漏三数之和这类题漏掉去重不会报错但会让输出结果包含重复组合在面试官眼里这就是代码不够严谨。去重的关键点有三个固定元素去重、找到答案后左指针去重、右指针去重。三个去重的位置缺失任何一个都可能产生重复答案。建议把这道题多写几遍直到三个去重条件的位置都形成肌肉记忆。5.4 单调性前提双指针不是万能的这是我最想强调的一点。双指针能带来 O(n) 的复杂度靠的不是魔法而是数据本身的单调性或有序性。如果数组无序对撞指针就无法判断和大了该往哪边移动如果问题需要穷举所有组合滑动窗口也无法覆盖不连续的子序列。所以拿到新题的第一件事不是想能不能用双指针而是先分析题目数据有没有能利用的结构。这也是为什么很多题解上来先做一步排序——排序的 O(n log n) 让数据获得有序性双指针才能发挥作用。面试时如果你能主动解释这里先排序是为了给对撞指针创造单调性条件会比直接背模板显得专业得多。5.5 滑动窗口与哈希表的配合滑动窗口常常需要配合哈希表来记录窗口内的状态。这里我踩过的一个坑是窗口收缩时需要同步更新哈希表里的计数并且一个字符的计数从 1 变为 0 时要不要从哈希表里删除这个键取决于你后续的判断逻辑。如果完全依赖 valid已满足的字符种类数来判断计数不会影响 valid 的判断删除不删除都能跑通但如果写的是if len(window) len(need)那计数为 0 的键就必须删掉否则会误判窗口已经覆盖了全部字符。这个细节很容易让代码看起来对实际错调试的时候一定要留意。6. 一套适合自己的双指针刷题顺序很多读者问过我双指针的题太多了从哪开始刷比较合理我根据自己带过新人刷题的经验建议按下面的顺序来先做两数之和有序数组版理解对撞指针的最小模型再做三数之和理解去重逻辑做验证回文串练习字符串里的对撞与边界处理做最长无重复子串进入滑动窗口领域做最小覆盖子串理解窗口合法性的哈希统计做环形链表和环形链表 II掌握快慢指针的数学原理做链表中间节点巩固快慢指针的步长控制最后挑战滑动窗口最大值把双指针和单调队列结合。这个顺序的用意是先用最简单的题目建立双指针的直觉再逐步叠加复杂度让每个新知识点都建立在之前已经理解的基础上。不建议一上来就去啃最小覆盖子串那是滑动窗口里的高阶题新手很容易被哈希表和 valid 计数绕晕。我自己在实际做题时还有一个习惯每做完一道双指针题会在题目旁边写一句这题为什么能用双指针。比如因为数组有序和的大小可以指导指针移动因为要求连续子串天然适合滑动窗口。这个习惯帮我建立了题目特征和算法之间的映射遇到新题时能更快地判断该往哪个方向想。另外建议准备一个错题本电子笔记就行把每次提交失败的边界案例记下来。你会发现双指针的 bug 类型其实非常集中主要就是越界、边界条件判断错误、去重遗漏。记几道题之后这些坑就再也难不住你了。最后再分享一个个人经验双指针的代码看起来短但真正在面试中写对、写快是需要刻意练习的。我见过太多人看题解秒懂自己写就废原因就是刷题时只看不写。建议至少手写十道以上的双指针题每道题都完整跑通再谈熟练。等你练到能一边写代码一边解释这里用左闭右开区间是为了方便处理空区间这个级别双指针这块就算是真正过关了。