前两天帮一个学弟模拟面试我问他一个升序整数数组找两个数使它们的和等于 target你会怎么做他几乎没犹豫就答了哈希表时间 O(n)。这个答案没错但我紧接着追问了一句数组有序这个条件你完全没用上能把它优化到 O(1) 空间吗他卡住了。那一刻我就想起自己当年刷题的样子——双指针的题见一道记一道却始终没想明白它为什么能跳着走、为什么不会漏掉答案。后来刷多了才悟出一个道理双指针不是某个题目的特殊技巧而是一类“用两个下标维护单调信息”的通用思路覆盖了二分之外的另一大块线性题型。这篇文章就是对双指针相关题型的一次完整梳理从对撞指针、快慢指针到滑动窗口把原理、典型题、易错点串在一起适合准备算法面试的读者也适合想系统整理这类题型的竞赛党。1. 双指针为什么能在有序数组上大胆跳一次单调性推导很多人背下了双指针的代码模版却解释不清“为什么 cur target 时移动 left 而不是 right”。我想先从这道最基础的题讲清楚因为后面所有对撞指针的题靠的都是同一个推导逻辑。1.1 从两数之和看指针移动的依据题目条件是升序数组假设当前左右指针对应left和right两数之和为curcur target说明总和太小。此时如果右指针向左移总和只会更小更达不到 target所以唯一可能的方向是 left 向右移把当前的 left 这个值排除掉。cur target对称地总和太大左指针向右移只会更大所以只能右指针向左移。代码写出来只有十几行def two_sum_sorted(nums, target): left, right 0, len(nums) - 1 while left right: cur nums[left] nums[right] if cur target: left 1 elif cur target: right - 1 else: return [left, right] return []关键在于每次比较之后我们不是随便选一个指针移动而是根据单调性排除了一个方向。left每次右移代表“以当前 left 为左端点的所有组合都不可能成为答案”right 每次左移同理。这样每次排除一行或一列候选解整个过程是 O(n)。1.2 去掉有序这个大前提双指针立刻失效为什么有序这么重要如果没有有序性cur target时右指针向左移后总和也可能变大右指针处换成一个更大的数单调关系被打破你就说不出哪个方向是安全的双指针自然不成立。我给学员举过这个反例数组[7, 1, 5, 2]target 是8双指针从两端扫会得到7 2 9 8于是 right 左移结果7 5 12继续左移最后返回空数组——但它明明有解7 1 8。问题不在双指针而在我们没有前提条件。所以判断一道题能不能用双指针核心就一条你能不能为每一步移动找到一个“必不可能”的排除依据。这也是面试官想听的东西比背代码值钱得多。往后遇到的所有双指针题本质都是围绕这条在建模。2. 对撞指针的经典题型从两数和到三数去重再到盛水容器对撞指针是最容易理解的一类双指针一个从数组头部往右走一个从尾部往左走直到相遇。除了最简单的两数之和三数之和、四数之和、盛最多水的容器、接雨水这些高频题全都属于对撞指针的变形。2.1 三数之和的去重细节外层和内层两次陷阱三数之和要求返回所有不重复的三元组且三元组和为零。我的经验是这题九成人第一次提交都挂在去重上而返工点就两个位置外层循环的去重。固定第一个数nums[i]后内层用双指针在i1到末尾找两数。外层去重要写成跳过nums[i] nums[i-1]的情况而不是nums[i] nums[i1]。后者会把[-1, -1, 2]这种有效组合直接漏掉因为第一个数已经被你当成重复值跳了。内层找到一组解后的去重。找到[nums[i], nums[left], nums[right]]后左右指针必须继续内缩并把和当前解重复的值全部跳过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 left, right i 1, n - 1 while left right: s nums[i] nums[left] nums[right] if s 0: left 1 elif s 0: right - 1 else: res.append([nums[i], nums[left], nums[right]]) left 1 right - 1 while left right and nums[left] nums[left - 1]: left 1 while left right and nums[right] nums[right 1]: right - 1 return res内层跳过重复值的两个 while 一定要放在“找到一组解”之后而不是每次移动都判断。很多简化版代码为了图省事在s 0和s 0的分支里也写去重这会把指针移动逻辑搅乱一旦遇到全零数组就可能出现 left 越过 right 还在死循环的诡异情况。2.2 盛水容器与接雨水判断依据不是大小而是“短板移动”三数之和这类题指针移动依据是“数字之和偏大偏小”属于比较容易想到的方向。可盛最多水的容器就不一样了它的比较对象是两根柱子的高度def max_area(height): left, right 0, len(height) - 1 ans 0 while left right: area (right - left) * min(height[left], height[right]) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ans这题我第一次看答案时有个很大的困惑为什么移动较矮的一侧就一定不会漏掉最优解后来想通了当前面积由left和right之间距离乘以矮柱高度决定。如果保留矮柱、移动高柱底边距离要么变短、要么最多持平而高度上限不变面积不可能超过当前值反过来移动矮柱才有机会遇到更高的新柱让面积变大。这不也是排除思想吗移动高柱那一步对应的所有候选面积都被“不可能超过当前面积”这个理由排除了。接雨水在思路上和盛水容器有亲缘关系都是左右维护边界最大值。双指针解法里维护left_max和right_max哪边小就处理哪边当前位置的积水量。这一题我没有放完整代码因为它的难点已经从“指针移动依据”转移到了“边界最大值的滚动维护”上建议你手写一遍双指针版本再和动态规划版本对比一次能明显加深对“单调性从哪来”的理解。3. 快慢指针先分清链表的环入口再做数组原地覆盖快慢指针和对撞指针最大的不同是方向两个指针同向而行速度不同或职责不同。链表题和部分数组题会让它发挥奇效尤其是空间受限的场景。3.1 环检测与环入口那个经典的数学推导其实很朴素链表判环是最被滥用的“背答案”题之一常见解法如下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原理其实很直白如果链表有环快指针每次比慢指针多走一步相当于在环形跑道上有一个速度差那么快指针终会追上慢指针。注意循环条件必须写fast and fast.next否则当链表演变成单节点时访问fast.next.next会直接抛空指针异常。如果面试官继续追问“怎么找环的入口”很多人就开始在纸上画圈了。设头节点到环入口的距离为 a入口到第一次相遇点的距离为 b环一周长度为 c。慢指针走过a b快指针走过a b k*c又因为快指针速度是慢指针的两倍所以2(a b) a b k*c整理后得到a k*c - b。这个式子的含义是从第一次相遇点继续前进a的距离恰好能回到环入口。于是实现方案就一句话相遇后把一个指针放回头节点另一个留在相遇点两个指针都以一步一个节点的速度前进再次相遇的位置就是环入口。def detect_cycle(head): slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: slow head while slow ! fast: slow slow.next fast fast.next return slow return None我强烈建议把这段推导写在纸面上自己推一遍而不是只记“slow 放回头节点”这个结论。面试时能推出a k*c - b的人和只会背代码的人给面试官留下的印象完全不同。3.2 数组原地去重和移动零快慢指针的另一身份是“接手扫描”链表中的快慢指针确实体现为速度快慢不同但数组里的“快慢指针”更准确的说法是“两个职责不同的下标”。以原地去重为例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这里的slow维护“已处理的结果区间的末尾位置”fast负责遍历整个数组。遇到一个新的唯一值时先把 slow 前进一位再写入新值。这个写法的妙处是空间 O(1)时间 O(n)而且不破坏相对顺序。移动零也是同一副面孔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我真见过有人在这道题上绕远路先数零的个数再删零再补零写了半个多月没写利索。实际上把非零元素“筛”到前面剩下的位置自然就是零。每次遇到面试者我都会提醒一句看到“原地”“保持顺序”“常数空间”这些要求时先下意识想想能不能用两个下标分角色解决这通常就是双指针在数组题里最典型的信号。4. 滑动窗口是双指针的第三副面孔识别与框架很多刷题教程把滑动窗口和双指针分成两个专题其实从实现上看滑动窗口就是两个同向指针——left 表示窗口左边界right 表示窗口右边界并且在逐步推进。你甚至可以把它理解成一种特殊的快慢指针。只是它的考点集中在“窗口内状态的维护”上。4.1 无重复最长子串和最小长度子数组的框架拆解先看“长度最小的子数组”这道题给定一个正整数数组和一个 target找满足和大于等于 target 的最短连续子数组。def min_sub_array_len(target, nums): left 0 total 0 ans float(inf) for right, x in enumerate(nums): total x while total target: ans min(ans, right - left 1) total - nums[left] left 1 return 0 if ans float(inf) else ans框架非常清晰右指针扩张把新元素纳入窗口一旦窗口满足条件就用 while 不断收缩左边界直到条件再次不满足收缩过程中记录最优值。为什么收缩用 while 而不是 if因为可能收缩一个元素之后窗口依然满足“和 target”需要继续收缩才能找到最短长度。再看“无重复字符的最长子串”这个题的代码很短坑却很隐蔽def length_of_longest_substring(s): last {} left 0 ans 0 for right, ch in enumerate(s): if ch in last: left max(left, last[ch] 1) last[ch] right ans max(ans, right - left 1) return ansright 每次向右扩展并记录字符最后一次出现的位置left 代表当前窗口左边界。当遇到重复字符时直接把 left 跳到“该字符上一次出现位置的右边”即可窗口内就必然没有重复字符了。这两道题一加一减覆盖了滑动窗口的两大典型目标求最短满足条件窗口、求最长满足条件窗口。4.2 窗口状态维护的坑位left 的跳跃更新为什么用 max无重复字符那题新手最容易写错的一行是left last[ch] 1而不是left max(left, last[ch] 1)。看这个反例字符串abba扫描到第二个a时last[a] 0如果你直接让left 1窗口就从 1 开始了但此时 left 原本已经在位置 2因为之前遇到重复b时已经跳到 2这一下又把 left 拉回去了窗口变成了bba包含重复字符。所以必须用 max 保证 left 只前进、不后退。这个细节不对代码在abba这类字符串上就会给出错误答案。我刷这道题时至少被这个反例教育过两次所以现在每讲滑动窗口都会单独把它拎出来。再说最小覆盖子串这类困难题框架本质上还是“right 扩张 left 收缩 窗口合法性判断”只是需要用一个计数哈希表维护“还需要多少个目标字符”。很多题解把它写得特别复杂但你抓住三个组件就够了需要的字符计数、当前窗口覆盖计数、以及为了判断当前窗口是否合法而维护的“已达标目标字符种类数”。只要这三件套在窗口类难题的框架都是一致的。5. 我把双指针踩过的坑做成了这张检查单刷双指针的题画风通常是这样的思路懂了代码写出来一跑测试有死循环有边界越界有结果重复。这些年我积累了一张自己的检查单每次写完相关代码就照着过一遍。5.1 循环边界和死循环的类型化处理第一类坑是循环条件写错。对撞指针用while left right快慢指针判环用while fast and fast.next。这个条件决定访问 nums[right]、fast.next 这类字段是否安全必须放在循环体第一层就防住。第二类坑是某个分支没有推进指针。比如三数之和的三层循环里有人会忘记在s 0时同时移动左右指针导致同一组解被反复收集甚至进入死循环。我自己的习惯是每写一个分支都问一句“这个分支会不会让 left 和 right 都原地不动”。只要有任何一条路径是原地踏步就会出现死循环。第三类坑是去重时漏了“至少移动一次”这件事。拿到一个有效解后正确顺序一定是先left 1; right - 1再去跳过重复值。如果一上来就在 while 里跳重复遇到区间内全是相同数字时left 可能根本没动直接死循环。检查单里我加了这一条任何跳过重复值的循环前面必须有一次无条件移动。5.2 面试追问的三个高频场景备好推导别背答案双指针像一个包装精美的框架但面试官真正想考察的是你的排除思维。我自己总结过最常被追问的三个点第一三数之和为什么要先排序因为双指针依赖有序性来排除候选排序付出的 O(n log n) 成本换来内层 O(n) 的扫描总复杂度优于暴力三层循环 O(n^3)。第二环形链表中为什么 fast 一定能追上 slow因为每轮 fast 比 slow 多走一步环内相对距离每次减少 1不会出现“跨过”而不相遇的情况最终必定逼近到相遇。第三滑动窗口里 left 为什么可以用 max 来更新因为窗口的左边界不能回退如果直接用重复字符上次出现的位置会破坏窗口的单调性。这三次追问我分别在真正的技术面里遇到过前两个。每次都庆幸自己推过数学式子而不是只背了答案因为面试官一定会层层加挖追上了之后呢入口在哪能证明吗5.3 按题型分组刷题的思路如果让我给准备算法面试的人一个具体的刷题路线我会说别按题号刷按题型分组对撞指针组两数之和 II、三数之和、四数之和、盛最多水的容器、接雨水、有效回文串。快慢指针组环形链表、环形链表 II、链表中点、删除链表的倒数第 N 个节点、原地去重、移动零。滑动窗口组无重复字符的最长子串、长度最小的子数组、字符串排列、最小覆盖子串、水果成篮。每组先做两道代表题把原理吃透再处理变形题。泛刷一百道的效果远不如把五道题的各种变体和面试追问自己推一遍。我在带新人的时候还会让他们每道题写一行注释记录“这一步移动的排除依据是什么”写不出注释说明还没想明白这题就不算做完。最后再分享一个我个人的小习惯刷完一类双指针题之后我会合上代码在纸上重新推导一遍“为什么可以这么做”。比如两数之和的排除逻辑比如环入口的等距推导比如滑动窗口 left 不回退的原因。隔三差五复述一次比考前临时翻题解可靠得多。你的目标是应付真实面试环境而不只是把 LeetCode 的测试用例跑绿——双指针这类题真正练的其实是“想到什么情况可以安全排除”的建模能力代码本身只是最后一公里。