双指针这类题说难不难说简单也不简单。我在刷题库和带人准备面试的过程中发现很多人要么是见过套路但一改条件就懵要么是知道双指针这个词却分不清什么时候应该用快慢指针、什么时候用左右指针、什么时候用滑动窗口。其实双指针并不是某种高深的算法它本质上是一种暴力解法的优化策略核心是让两个指针在数组或链表上做有序的移动从而把时间复杂度从 O(n²) 降到 O(n)或者在链表场景里避开哈希表的额外空间。这篇文章我打算把双指针相关的常见题型做一个系统拆解从底层原理到具体代码再到我实际踩过的坑尽量让你能形成一套自己的解题模板。如果你正在准备算法面试或者刚刷完链表、数组的入门题想往进阶走这篇文章应该能帮你省下不少自己摸索的时间。我会按照左右指针、快慢指针、滑动窗口三个大类来讲每一类都会配典型题目、思路推导、代码实现和易错点。最后还会聊聊刷题顺序以及怎么把模板固化下来。1. 双指针到底是什么从暴力到优化的思维跃迁1.1 指针不是指针双指针的核心思想先澄清一件事这里的“指针”不是 C 语言里那个存放内存地址的指针而是一个广义的“位置标记”。你在数组上可以用两个整数下标来充当指针在链表上可以用两个节点引用来充当指针。它们共同组成一个窗口、一个区间或者一对逐步逼近的游标帮你把原本需要多层循环枚举的状态空间压缩掉。为什么能压缩关键在于数据本身具备某种“单调性”或者“顺序性”。举个例子在一个升序数组里找两个数使得它们的和等于目标值。暴力做法是枚举所有二元组时间复杂度 O(n²)。但如果你用两个指针一个放在开头一个放在结尾根据当前和与目标值的大小关系来决定移动哪个指针每次判断都能排除掉一大片不可能的组合这就是优化的本质。这个思想特别像生活里两个人在一条窄巷子里相向而行如果两个人距离太近就说明需要往外退一步如果太远就说明需要往里进一步。整个过程里两个人不会回头也不会交叉所以总共走的步数不超过 n 步。用一种更本质的话说双指针让“状态转移”变得有方向而不是盲目枚举。1.2 双指针的三大基本形态左右、快慢、滑动窗口我习惯把双指针题型分成三类这样看到题目能快速定位。当然这种分法不是绝对的但足够应付绝大多数面试场景。第一类叫左右指针也叫对撞指针。两个指针分别从数组的两端出发相向移动。典型场景是在有序数组上求解两数之和、三数之和、判断回文串、盛水最多的容器等。核心特征是数组/字符串具有单调性而且需要在一段区间内寻找某种约束条件下的最值或解。第二类叫快慢指针。两个指针从同一端出发一个移动速度快一个移动速度慢。典型场景是链表找环、找中间节点、找倒数第 k 个节点以及数组的原地去重或移动特定元素。核心特征是需要利用速度差来制造“相遇”或“距离差”从而定位特殊位置。第三类叫滑动窗口。本质上也是双指针但两个指针通常朝同一个方向移动像拉链一样维护一个动态区间。典型场景是求最长/最短子串、子数组满足某种条件。核心特征是窗口内的元素集合可以用一个计数器维护窗口扩张和收缩都有明确的条件。这三种形态不是孤立存在的。滑动窗口就是同向双指针左右指针是对撞双指针快慢指针可以看成链路上的双指针。理解它们的共同点比背套路更有价值双指针能成立的底层逻辑要么是区间有序要么是窗口内信息可以增量维护要么是路径上存在速度差导致的确定性位置。抓住这一点很多变形题你都能现场推导出来。2. 左右指针题型有序数组与二元组的收缩艺术2.1 两数之和的变形从哈希到双指针最经典的入门题是给定一个升序数组和一个目标值找出数组中两个数的下标使得它们的和等于目标值假设只有唯一答案。哈希表解法人人都会遍历一遍用哈希表记录“目标值减去当前值”再判断后续是否遇到。时间复杂度 O(n)空间复杂度 O(n)。但如果你面对的是一个有序数组并且题目要求你不能用额外空间双指针就是更优的选择。写法非常固定def two_sum(nums, target): left, right 0, len(nums) - 1 while left right: s nums[left] nums[right] if s target: return [left, right] elif s target: left 1 else: right - 1 return []这个代码里有一个隐藏的优化逻辑数组有序时如果两数和小于目标说明 left 位置太小和任何 right 右边的值配合都不可能满足需求因为 nums[right] 已经是右边最大的了只能把 left 往右移动。反之如果和大于目标说明 right 太大需要往左移动。每次排除的是一整个维度上的候选解所以整体是 O(n)。这里我要提醒一个细节有些题会把数组改成无序这时候双指针就失效了。遇到无序数组第一时间考虑哈希表除非题目要求你“在排序过程中不能改变原数组”否则也可以先排序再使用双指针但排序本身是 O(n log n)要和哈希的 O(n) 做权衡。实际面试中如果输入是排序好的考察点通常就是双指针如果不是排序好的有时候也需要你自己把数组拷贝一份并记录原下标这时候复杂度会上升要跟面试官讲清楚。2.2 三数之和去重才是难点三数之和可以看作两数之和的外层加了一层循环。题目是给定一个整数数组找出所有和为 0 且不重复的三元组。如果你只想到暴力三层循环那复杂度是 O(n³)。改进的思路是固定其中一个数剩下的部分就变成了有序数组上的两数之和。前提是先对数组排序然后外层 i 从 0 到 n-3 遍历内层用 left i1 和 right n-1 做双指针。伪代码结构是def three_sum(nums): nums.sort() n len(nums) res [] for i in range(n - 2): if i 0 and nums[i] nums[i-1]: continue target -nums[i] left, right i 1, n - 1 while left right: s nums[left] nums[right] if s target: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left1]: left 1 while left right and nums[right] nums[right-1]: right - 1 left 1 right - 1 elif s target: left 1 else: right - 1 return res这里最阴险的坑是去重。很多新手只会最后对结果列表去重却发现用了 set 之后结果仍然有重复或者因为去重逻辑不对直接跳出循环。去重必须做在“移动指针之前或之后的一步”而且要保证每移动到一个新的位置时该位置的值和上一个位置不同。外层 i 的去重要从 i1 开始判断 nums[i] nums[i-1]为什么不是 nums[i] nums[i1]因为你要保留当前 i 作为固定数如果和下一个数相同那么下一个数作为固定数时会枚举出完全一样的组合所以跳过相邻重复要从前一个判断。内层两个指针去重也一样为了在找到一组解后不重复收集相同的二元组必须把 left 和 right 都移动到下一个不重复的位置。三数之和的时间复杂度是 O(n²)空间复杂度是 O(log n) 到 O(n)取决于排序实现。它是面试中出现频率极高的题建议你手写至少三遍直到闭着眼都能把去重条件写对。2.3 更多收缩场景接雨水、最接近的三数之和左右指针的应用远不止求和。我再讲两个比较有代表性的盛最多水的容器和接雨水。盛最多水的容器题目是这样的有一组高度数组代表 x 轴上的一系列墙壁选择两个墙壁使得它们和 x 轴围成的容器能装的水最多。体积公式是 min(height[left], height[right]) * (right - left)。双指针怎么做一开始 left 在最左、right 在最右此时宽度最大。接下来要决定移动哪个指针如果移动高度较大的那一侧宽度会变小而 min 高度不会增大水面积必然减小如果移动高度较小的那一侧min 有可能变大面积才可能变大。所以每次比较左右高度移动矮的一侧。这个题的证明其实比代码重要理解了“矮边是瓶颈”以后类似思路的题你都能联想到。接雨水比盛水容器复杂一点。它要求计算下雨后能接住多少雨水。常见的解法有动态规划、单调栈但双指针同样能解而且空间复杂度 O(1)。核心是维护左右两个边的最大高度 left_max 和 right_max哪个方向的最大高度更小就往哪边计算当前位置的储水量。逻辑是这样的对于位置 i它能存储的水量取决于左右两侧最高墙中较矮的那个再减去当前墙的高度。用双指针从外侧向内推进因为外侧的较高墙已经能保证当前位置至少可以依赖那一侧的最大值。代码大概长这样def trap(height): if not height: return 0 left, right 0, len(height) - 1 left_max right_max 0 water 0 while left right: if height[left] height[right]: if height[left] left_max: left_max height[left] else: water left_max - height[left] left 1 else: if height[right] right_max: right_max height[right] else: water right_max - height[right] right - 1 return water这个题容易卡壳的地方在于为什么要更新 max 之后才计算因为 left_max 记录的是 left 已经扫过区域的最大值而不是全数组最大值。但巧妙的是由于我们只在 height[left] height[right] 时才结算左边此时右边存在一个比 height[left] 更高的墙所以当前位置的水量确实由 left_max 决定。反过来也一样。这个解法是双指针中的一个亮点建议配合图去理解别只背代码。3. 快慢指针题型链表与循环检测的不二法门3.1 链表中间节点与环检测快慢指针在链表题里几乎是无敌的存在。最基础的应用是找链表的中间节点两个指针同时从 head 出发快指针每次走两步慢指针每次走一步当快指针走到末尾时慢指针刚好在中间。这里有个细节如果节点总数是偶数到底返回哪个中间节点这取决于循环条件。如果你写成 while fast and fast.next那么当 fast 走到最后一个节点时停止慢指针会落在偏右的中间节点上。如果想要偏左的中间节点需要调整条件为 while fast.next and fast.next.next。很多题目会明确要求返回第一个中间节点还是第二个读题一定要仔细。环检测可能是快慢指针最有名的应用了。常见做法是从 head 出发快指针一次走两步慢指针一次走一步如果链表有环那么快慢指针一定会在环内相遇。如果没有环快指针会先遇到空节点。这个解法的正确性有数学支撑我后面再展开。这里先给出基本检测代码def has_cycle(head): slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False很多初学者会担心万一快指针直接跳过慢指针怎么办答案是在每次移动一步的模型里不会发生。因为快指针每次比慢指针多走一步在环内它们之间的距离会从某个值逐渐变化每轮减 1不会出现从 1 跳到 -1 的情况只会在 0 的时候相遇。你可以想象两个人绕操场跑步速度快的人每次都比慢的人多跑一小步最终套圈时一定会并排。3.2 寻找环入口的数学推导很多文章只给结论“相遇后把慢指针放回头部再和快指针同时一步一步走再次相遇时就是环入口”。但如果你不知道为什么很容易在变形题里翻车。我把推导过程重新走一遍。假设链表从 head 到环入口的节点数为 a环长度为 b。当快慢指针第一次相遇时设慢指针走了 s 步快指针走了 2s 步。同时快指针比慢指针多走了若干个环的长度假设多走了 k 圈那么有 2s - s k * b即 s k * b。慢指针从 head 到相遇点的距离是 a x其中 x 是环入口到相遇点的距离按前进方向。所以 a x k * b。关键推导来了如果从 head 重新出发一个指针让它一步一步走 a 步到达环入口同时让原来的慢指针从相遇点继续往前走。因为慢指针现在已经累计走了 s k * b 步它再走 a 步总共走了 k * b a。这个总步数对环长度 b 取模等于 a 对 b 取模。也就是说慢指针再走 a 步时它在环内的位置距离环入口正好是 a 的余数这里需要更严谨地说明相遇时慢指针在环内距离入口为 x而从入口走 a 步后在环内位置相当于入口 a但由于环的周期性与某个位置重合。实际上最终相遇点可以证明就是入口。更简洁的证明是相遇时让另一个指针从 head 以相同速度出发慢指针也继续走。当新指针走到环入口时走了 a 步此时慢指针总共走了 s a k * b a 步相当于从相遇点又前进了 a 步。而在环内慢指针距离环入口的距离是 x前进 a 步后的位置是 x a 对 b 取模。由 s a x k * b 可得 x k * b - a所以 x a k * b对 b 取模为 0也就是环入口。因此两个指针会在入口相遇。这个证明过程中a 不一定小于 b但取模结论一样成立。代码实现时找到相遇点后把 fast 重新指向 head然后两个指针都每次移动一步再次相等时返回即可。这个题在面试里属于“会者不难难者不会”能把推导讲清楚是很加分的。3.3 快慢指针在数组中的应用移除元素与原地重排快慢指针不只在链表上能用在数组上同样好用。比如原地删除有序数组中的重复项题目要求你把一个排序数组原地去重并返回新长度。这时定义 slow 为“已处理区域的最后一个位置”fast 负责扫描整个数组。当发现 nums[fast] ! nums[slow] 时说明遇到了新元素先 slow 1然后把 nums[fast] 赋值给 nums[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 1类似的还有移动零把数组里所有 0 移到末尾同时保持非零元素的相对顺序。解法是慢指针指向当前可以写入非零元素的位置快指针扫描遇到非零就交换或赋值。这种题在面试中往往是作为“热身题”出现的但千万不要觉得简单就掉以轻心。很多人会写成两个循环先数零再后移不但代码冗长还容易数组越界。用快慢指针一次遍历就能解决而且逻辑足够清晰。4. 滑动窗口题型子串与子数组的最优解4.1 滑动窗口的本质与框架滑动窗口解决的是“连续子数组/子串满足某种条件”的问题。它之所以能用双指针是因为对于固定端点随着另一端向右移动区间内的某种统计量是单调变化的。例如子串长度越长字符种类越多或数量越多子数组和越大。这种单调性使我们可以用 left 和 right 两个指针维护一个“可行窗口”并通过收缩左边界来寻找最优解。先看一个基本框架以“求满足条件的最短子数组”为例left 0 cur 0 ans 无穷大 for right in range(n): cur nums[right] # 扩展窗口加入 right 位置元素 while cur target: # 窗口满足条件时 ans min(ans, right - left 1) cur - nums[left] # 收缩窗口移除 left 位置元素 left 1这个框架的精髓在于for 循环负责移动右边界内层 while 负责收缩左边界收缩的前提是当前窗口已经满足题设条件。每次收缩前记录一个答案就能在 O(n) 时间内找到所有可行窗口中的最优解因为每个元素最多进窗口一次、出窗口一次。使用滑动窗口时一定要搞清楚“什么时候扩大右边界”“什么时候收缩左边界”“收缩到什么程度”这三个问题。大多数题目的变体都围绕这三者展开。比如有的题要求窗口内最多允许两种不同字符收缩条件就是“字符种类超过 2”有的题要求窗口内所有字符出现次数都大于等于某个阈值收缩条件极端复杂。所以框架只是骨架真正需要写清楚的是窗口内的计数逻辑和收缩条件。4.2 最小覆盖子串与字符串排列最小覆盖子串是一道非常经典的滑动窗口题。题目是这样的给定字符串 S 和 T请在 S 中找到包含 T 全部字符的最短子串。注意 T 里的字符可以重复例如 T AABC那么子串至少需要两个 A、一个 B、一个 C。解题思路是维护两个哈希表need 记录 T 中每个字符需要的数量window 记录当前窗口内各字符的数量。还有一个变量 matched 表示当前窗口内有多少种字符已经满足需求。right 向右扩展加入字符后如果 window[c] need[c]matched 加一当 matched len(need) 时说明窗口已经覆盖 T然后开始收缩左边界尝试找到更短的子串。收缩时如果移除一个字符使 window[c] 从 need[c] 变成了 need[c]-1matched 减一结束收缩。这种写法避免了遍历 need 来判断是否满足条件把判断复杂度从 O(k) 降到 O(1)整体保持 O(n)。实现里有个革命性的小技巧T 中不存在的字符根本不需要计入 window可以直接忽略因为它们不影响任何 need 条件的满足。这样想能极大简化代码。另一道常见题是“字符串的排列”判断 S 中是否存在一个子串是 T 的排列。其实可以看成固定窗口长度等于 len(T) 的滑动窗口只需要维持窗口大小恒定移动右边界的同时强制收缩左边界保证窗口长度不变然后 check 窗口内各字符计数和 T 是否完全一致。这里也可以用 matched 来优化。这两道题的核心细节在于窗口内的计数更新和 matched 变量的增减要在合适的时间进行。我见过太多人把 matched 的更新放在错误的位置导致结果多一个字符或少一个字符。建议你在纸上模拟整个流程几次尤其是窗口收缩时 matched 何时减一要确定是在更新计数之前还是之后。通常的做法是移除 left 指向的字符前先判断 window[char] need[char]如果是则 matched--然后 window[char]--最后 left。顺序不能反。4.3 无重复字符的最长子串窗口收缩的技巧这道题几乎是滑动窗口的代名词给定一个字符串找出其中不含重复字符的最长子串的长度。朴素想法是枚举所有子串并判断有无重复显然不可取。用滑动窗口的话left 指向窗口左端right 向右扩展。为了判断窗口内是否有重复字符需要用一个 set 或哈希表记录当前窗口内的字符。当 right 位置的字符已经出现在窗口内时就需要不断收缩 left直到把重复字符移除。但这里有一个更优的变体用哈希表记录每个字符最近一次出现的位置一旦发现当前字符在窗口内出现过直接把 left 跳到该字符上次出现位置的下一个位置。这样连内部的 while 循环都省了。标准写法可以这样def length_of_longest_substring(s): pos {} left 0 ans 0 for right, ch in enumerate(s): if ch in pos and pos[ch] left: left pos[ch] 1 pos[ch] right ans max(ans, right - left 1) return ans这里的核心是 pos[ch] left 这个条件。为什么要判断因为 pos 表里记录的是字符最近一次出现的全局下标可能已经落在当前窗口左边了。比如字符串 “abba”当处理到最后一个 a 时pos[a] 等于 0但 left 已经变成 2此时如果直接把 left 跳到 1就错了。所以判断“该字符上次出现的位置是否在窗口内”至关重要。这个细节几乎每个人都会踩一次我在这里特意强调。这种用“位置跳跃”代替“逐步收缩”的优化让时间复杂度仍然是 O(n)但常数更小也更容易写对。遇到类似“窗口内字符种类受限”的题目时也可以借鉴这个思路用一个 map 记录每种字符最近位置从而快速调整 left。5. 双指针的实际编写细节与调试经验5.1 边界条件与循环不变量写双指针代码最忌讳的是没有想清楚“循环不变式”。每次 while 循环开始前你的 left 和 right 分别代表什么区间是开区间还是闭区间这决定了循环条件和更新时间。我用一个统一习惯来避免这类问题对于左右指针我定义区间为 [left, right]初始 left 0right len(nums) - 1循环条件是 left right退出时 left right。移动时 left 或 right--不会出现 left right 的情况。对于快慢指针在数组上我定义慢指针 slow 表示“当前最后一个满足条件的元素的下标”初始为 0快指针从 1 开始扫描。对于滑动窗口我定义窗口为 [left, right]也就是当前窗口包含 left 和 right 两个端点的元素。初始 left 0for right in range(n) 逐个加入内层 while 收缩 left。只要循环不变量统一你就不会在“要不要加 1”“要不要减 1”上反复纠结。写代码前先用注释把每个变量的含义写清楚这是一种成本极低的防错手段。我经常建议身边刷题的朋友把变量名改得更有语义感比如 left、right、slow、fast稳妥远胜于用 i、j、k。虽然缩短代码很酷但浪费大量时间调试的时候就会后悔。边界条件还有一个容易出错的地方空数组、只有一个元素的数组、两个元素都相同或都不同的情况。不要把这类用例留到最后再测先想清楚你的代码在这些输入下是否会越界。比如 while fast and fast.next 这个条件就是专门保护 fast.next 不越界的。5.2 复杂度优化与空间权衡双指针算法最大的吸引力就是能把 O(n²) 降为 O(n)但同时你也要注意空间复杂度。有些写法虽然时间优化了但申请了额外的集合或哈希表空间仍是 O(n)。面试中如果面试官明确要求“原地”就要避免使用额外的大结构。举个例子链表环检测的快慢指针解法空间复杂度是 O(1)而用哈希表记录访问过的节点空间是 O(n)。当链表规模巨大时快慢指针显然更优。另一个例子是“旋转数组”相关的题目有些可以用翻转实现有些需要双指针加额外数组。选择时要想清楚约束优先级通常优先保证时间最优再尽量压空间。还有一点双指针不是在所有数据下都一定比暴力好。如果数组没有单调性、字符串没有窗口统计特性强行用双指针可能得到错误结果。比如让你在无序数组中找两个数使得和为目标值排序后用双指针虽然能过但排序破坏了原数组下标如果题目要求返回原下标就需要额外记录下标或使用哈希。这是很多公司喜欢设置的“陷阱”看起来很容易用双指针其实考察的是你能否判断它是否适用。5.3 常见错误与排查实录我把自己和身边人写双指针题时踩过的坑整理成了一张速查表希望你能避开。常见错误出错场景正确做法左右指针循环条件写成 left right两数之和、回文判断一般写 left right否则可能导致重复使用同一位置或越界快慢指针的 fast.next 未判空链表环检测、找中间节点while fast and fast.next 双条件保护三数之和去重位置错误结果出现重复三元组移动指针前/后都要跳过连续相同值且外层 i 去重要用 nums[i] nums[i-1]滑动窗口收缩时 matched 更新顺序错误最小覆盖子串先根据当前窗口计数判断是否匹配再更新计数再移动 left使用位置跳跃时忘了检查 pos[ch] left无重复字符最长子串必须检查上次位置是否在当前窗口内卸载边界输入时数组越界数组长度小于 2开头添加 if len(nums) 2 return ...排查双指针 bug 还有一个通用方法打印每次循环时的 left、right或 slow、fast、窗口状态在纸上模拟一个很小的案例。比如长度为 5 的数组手动走一遍看看变量在每一步是否符合预期。尤其是滑动窗口的 matched 变量打印窗口内容比单步跟踪更快。6. 刷题路线与训练建议6.1 从易到难的题型排序如果你想系统掌握双指针不要从“接雨水”这种难题开始那会摔得很惨。我建议按以下路线循序渐进基础抄写层两数之和有序版、移除元素、移动零、反转字符串。这四道题帮你建立左右指针和快慢指针的基本感觉。链表专项链表的中间节点、环形链表、环形链表入口、相交链表。这些题主要练快慢指针的调度与数学证明。滑动窗口入门无重复字符的最长子串、字符串的排列、定长子串的最大平均数。理解窗口扩张与收缩的时机。双指针进阶三数之和、四数之和、盛最多水的容器、接雨水。练去重和收缩策略。综合实战最小覆盖子串、长度最小的子数组、找出所有字母异位词。这类题结合了计数和窗口管理。我用这个顺序带过几个人效果比一上来刷难度列表要好因为每一道题都具备前一题的“铺垫能力”。6.2 如何总结属于你自己的双指针模板很多人喜欢收藏别人的模板但我更建议你亲手整理。整理的过程不是抄代码而是把自己对每个模板适用条件的理解写下来。比如我会在笔记里这样记录左右指针模板适用于有序数组或双端逼近问题。标志词是“排序数组”“唯一解”“最接近”。循环结构是 while left right。快慢指针模板适用于链表或数组原地操作。标志词是“环”“中间节点”“倒数第 k 个”“去重”。核心是速度比或写入位置。滑动窗口模板适用于连续子串/子数组最值。标志词是“最长/最短子串”“包含/不重复”。核心是窗口计数 收缩条件。每次做题后问自己三个问题为什么这题能用双指针如果用暴力会慢在哪里我的左右指针或窗口移动依据是什么把这些答案写在注释里而不是只保留代码。时间久了你自然能建立条件反射。我在实际刷题过程中还有一个习惯把同一类题目的变形放在一起做对比。比如把“三数之和”和“最接近的三数之和”放一起你会发现后者只需要维护一个最小差值去重逻辑可以简化把“无重复字符的最长子串”和“至多包含 K 个不同字符的最长子串”放一起你会发现后者把 set 换成了哈希计数收缩条件从“重复”变成“种类数超限”。这样的对比比机械性刷 50 道题有效得多。最后再分享一个我自己的体会双指针题型的代码量通常不大但思维量不小。很多时候你以为自己在调 bug其实是在反复确认自己是否理解“移动某个指针之后为什么另一个指针不需要回头”。如果能把这一点想透以后遇到再新的变形题你也能在五分钟内给出合理方案。希望这篇总结能帮你在双指针上少走弯路早日形成自己的解题模板。