如果你正在准备算法面试随便打开哪个刷题平台的高频题单“双指针”三个字一定是绕不开的常客。热词榜上它长期霸榜不是没道理——几乎所有主流面试题库里双指针标签下的题目数量都排在前面而且这个技巧本身也足够优雅不需要复杂的数据结构只要两个游标就能把一堆 O(n²) 的暴力解压到 O(n)。这篇文章不打算讲什么高深理论我想从一个刷题老手和面试官双重身份的角度把双指针这件事讲透它为什么高频、底层逻辑是什么、相向和同向两大门派怎么区分、五道必会高频题怎么拆解、以及我在实际刷题和面试里踩过的边界条件的坑。1. 双指针为什么是高频本质上是把搜索空间砍掉一大半1.1 暴力双循环的问题出在哪先看一个最经典的场景在有序数组里找两个数使它们的和等于 target。新手第一反应肯定是双重循环def two_sum_brute(nums, target): n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j] target: return [i, j] return []这段代码能跑但时间复杂度是 O(n²)。数组长度到 10⁵ 量级就是 10¹⁰ 次运算基本告别活路。问题的根源在于双重循环把每一对组合都枚举了一遍绝大多数组合根本不可能成为答案这些计算全部是浪费。面试官看到 O(n²) 的解法接下来的追问几乎是可以预判的能不能优化到 O(n) 而双指针就是回答这个问题的标准答案。1.2 指针移动的本质每次移动都淘汰一批不可能的组合双指针之所以能提速关键不在两个指针这个形式而在于有序性带来的淘汰逻辑。拿上面的例子说假设数组是升序的left 指向左端right 指向右端当前和nums[left] nums[right]小于 target。请问right 左侧的所有位置和 left 组合还有可能等于 target 吗不可能。因为数组有序nums[right]是当前右指针位置最大的值相对右侧区间而言右边如果再往左走值只会更小和固定 left 加出来的和只会更小离 target 越来越远。所以以 left 为左端点的所有候选组合在这一瞬间可以整体划掉。每次移动指针淘汰的是一整块组合而不是一个单独的组合。left 最多移动 n 次right 也最多移动 n 次总共 O(n) 次操作就能覆盖所有可能的答案区间。这就是双指针的底层逻辑——利用数据的有序性或单调性让指针的每次移动都有排除法的意义。1.3 双指针的两大门派相向与同向我刷题时习惯把双指针分成两类分类标准非常简单两个指针的移动方向。相向双指针对撞指针left 从数组头部出发right 从尾部出发两者向中间靠拢。典型场景是排好序的数组、需要夹逼判断的场景比如两数之和、三数之和、盛最多水的容器、回文串判断。同向双指针快慢指针/滑动窗口两个指针从同一端出发一个走得快一个走得慢或者一个负责扩展一个负责收缩。典型场景是原地去重、链表判环、连续子数组/子串问题滑动窗口本质也是同向双指针。这两类的判断方法我后面会展开讲。先说结论看到有序数组 求和/比较类题目优先想相向看到子数组、子串、链表环类题目优先想同向。2. 相向双指针两边夹逼的核心套路与三道高频题2.1 两数之和 II输入有序数组最标准的对撞模板力扣 167 是相向双指针的入门第一题也几乎是所有面试官检验你双指针基本功的第一题。完整解法def two_sum(numbers, target): left, right 0, len(numbers) - 1 while left right: current numbers[left] numbers[right] if current target: return [left 1, right 1] # 题目要求从 1 开始计数 elif current target: left 1 else: right - 1 return []整个循环的核心逻辑只有三行和太小就左边往右走和太大就右边往左走相等就返回。为什么这么移动是安全的刚才已经解释过了——有序数组里left 固定时right 往左走和只会变小反过来right 固定时left 往右走和只会变大。每走一步就排除掉一整片不可能的区域。很多人会忽略两个小细节。第一是循环条件left right不是因为两个指针不能指向同一个元素题目要两个不同的数。第二是返回下标是从 1 开始数的很多人刷的时候直接用原数组下标一提交就挂。2.2 三数之和排序 夹逼 去重的综合考验力扣 15 是面试里真正的分水岭。能写出两数之和的人很多但三数之和能把一大批人挡在门外核心难点是全去重。思路本身不复杂先排序固定一个数nums[i]然后在i1到数组末尾这段区间上跑两数之和用相向双指针。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 # 剪枝nums[i] 已经大于 0后面的数都更大不可能凑成 0 if nums[i] 0: break 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]]) left 1 right - 1 # 二层去重跳过重复的 left 和 right while left right and nums[left] nums[left - 1]: left 1 while left right and nums[right] nums[right 1]: right - 1 elif total 0: left 1 else: right - 1 return res我在这里踩过的坑是只做了第一层去重固定元素去重忘了在找到一个三元组之后对 left 和 right 去重。结果就是同一个三元组因为 left/right 的重复值反复出现提交直接超时或返回重复结果。第一次因为这个问题 debug 了半小时后来长记性了——去重一定是在找到结果之后立刻做而且要连跳两次。nums[i] 0直接 break 是个很好的剪枝技巧排序之后数组是升序的固定元素都大于 0 了后面所有数都不可能把和拉回 0再往后更不可能。这种剪枝在面试里主动提出来很加分。2.3 盛最多水的容器为什么永远只移动较短的那条边力扣 11 的表面形式是求面积但解法依然是相向双指针。这题最反直觉的地方在于两个指针一个指向左墙一个指向右墙面积 短边高度 × 宽度。每次到底该移动哪边直觉上很多新手会想移动长边试试因为长边高挪一下说不定遇到更高的。错。正确的策略是永远移动短边。证明其实很简单假设height[left] height[right]当前面积 height[left] * (right - left)。如果我们固定 left 不动把 right 往左移宽度必然变小而高度被短边height[left]死死压住——即使遇到的墙再高容器高度还是height[left]。所以所有left 不动、right 左移的组合面积都不可能超过当前值。唯一有机会让面积变大的是把 left 往右移去寻找一条更高的短边。def max_area(height): left, right 0, len(height) - 1 ans 0 while left right: area min(height[left], height[right]) * (right - left) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ans这题的时间复杂度同样是 O(n)空间 O(1)。面试官追问为什么移动短边是对的时能把这个短边限制高度移动短边才可能提升高度的论证讲清楚比背代码有用得多。3. 同向双指针快慢指针与滑动窗口的统一视角3.1 删除有序数组中的重复项快慢指针最基本的形态力扣 26 是我认为理解同向双指针最好的入手题。题目要求原地修改数组不能新建额外空间。解法是用一个 slow 指针维护已处理好的无重复前缀的末尾用一个 fast 指针扫描整个数组。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这里的不变量是nums[0..slow]始终是已处理部分中不含重复的序列。fast 每遇到一个新值就把它搬到 slow 的下一个位置。整个过程 fast 走一遍slow 跟着走两个指针同向运动快的负责探索慢的负责记录。这种快指针探路、慢指针写结果的模式在力扣 283 移动零、力扣 27 移除元素里几乎一模一样学会一道相当于会了三道。3.2 环形链表检测Floyd 判圈从追及理解快慢指针链表的快慢指针和数组略有不同但思想一脉相承。力扣 141 判断链表是否有环经典解法是龟兔赛跑——slow 每次走一步fast 每次走两步如果链表有环快指针最终会从后面追上慢指针。def has_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False为什么快指针走两步而不是三步其实走三步也能追上但步长差得越多编码时的空指针判断越麻烦。最稳的是步长差 1在环上fast 相对于 slow 的速度是 1 步/轮无论环多长追及过程都能保证在有限轮内相遇。如果步长差不是 1在某些环长组合下可能会跳过相遇点需要额外的数学处理得不偿失。这题的进阶版力扣 142要返回环的入口节点解法是在快慢指针相遇后把一个指针重置回 head两个指针各走一步再次相遇的位置就是入口。这个结论很多资料直接给了但面试时最好能说出理由相遇点到入口的距离 head 到入口的距离。能讲清楚这点的候选人基本是真正理解了 Floyd 判圈而不仅仅是背模板。3.3 合并两个有序数组从后往前的逆向双指针力扣 88 是一个很有意思的反例它用双指针但方向是从尾部往头部走。题目给了两个有序数组 nums1 和 nums2nums1 长度是 mn后面 n 个位置是空的要求把 nums2 合并进 nums1。如果从前往后合并nums1 的原元素会被覆盖掉因为有效的 m 个元素塞不满 mn 个位置从前填会先动前面的位置。所以正确做法是从后往前填def merge(nums1, m, nums2, n): i, j, k m - 1, n - 1, m n - 1 while i 0 and j 0: if nums1[i] nums2[j]: nums1[k] nums1[i] i - 1 else: nums1[k] nums2[j] j - 1 k - 1 # nums1 的前 m 个如果有剩余已经在正确位置只需处理 nums2 剩余 while j 0: nums1[k] nums2[j] j - 1 k - 1这也是双指针只不过夹逼的对象是数组的尾部和尾部移动方向从外向里变成从后往前。它提醒我一件事双指针的方向不是只有左到右和两端往中间要结合数据存储的位置灵活调整。面试中遇到原地合并这类题先想想哪个方向的覆盖不会丢数据。3.4 滑动窗口同向双指针的变体滑动窗口本质上是同向双指针right 指针负责扩张窗口left 指针负责在条件不满足时收缩窗口。以力扣 3 最长无重复字符子串为例def length_of_longest_substring(s): 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核心逻辑是right 扩展到一个新字符时如果它已经在窗口里说明重复了就不断移动 left 把重复字符从窗口里挤出去直到窗口干净。每一步窗口[left, right]内的子串都是无重复的取所有窗口长度的最大值。复杂度看起来有嵌套 while但 left 最多移动 n 次整体还是 O(n)。我在实际面试里发现很多候选人能背出模板但说不清为什么 left 不需要回头。原因正是同向双指针的单调性窗口收缩之后left 只会继续往右不需要回到之前的位置重新扩张因为之前的子串已经处理过了。4. 边界条件与调试双指针翻车的高发区4.1 while 条件里的 与 到底差在哪这是双指针初学者最容易翻车的地方面试里也经常有人当场卡住。我的经验是分场景记处理元素对的场景两数之和、三数之和、回文串判断用left right。因为 left 和 right 指向同一个元素时这一对不合法。二分查找场景用left right因为查找的是单个位置mid 位置本身可能是答案不能把它排除在外。滑动窗口场景内层收缩用while left right或while left right都可能出现取决于窗口是否允许为空。比如找最短覆盖子串时窗口可以空就要允许 left 超过 right。一个很实用的检查方法写出循环体之后看看如果 left 和 right 刚好相邻、刚好相等、刚好交叉程序分别会怎么走。这三个状态测一遍边界问题基本能暴露出来。4.2 指针移动的时机什么时候只动一个什么时候一起动以两数之和为例子current target时只移动 leftcurrent target时只移动 right这是确定的。但在三数之和里找到total 0之后left 和 right必须同时移动否则会出现两种情况只移动 left 的话新的组合以当前 right 为右边界可能又凑出一个和为 0 的组合但你不知道是该继续还是该停更糟糕的是如果你忘了移动直接死循环。还有个容易忽略的场景在盛最多水的容器里如果height[left] height[right]两边高度相等移动哪边都行但必须至少移动一个而且最好一次性跳过所有与当前边等高的位置这样能少算很多无意义的面积。我刷题时习惯写成if height[left] height[right]移动 left虽然另一侧的等值情况没被优化但不会出错。4.3 三条铁律 调试三板斧踩过足够多的坑之后我自己总结出双指针代码的三条铁律每次循环迭代至少有一个指针发生移动。这是终止性的保证。如果某条分支没有移动指针八成就是死循环的开始。在访问nums[left]或nums[right]之前确认指针还在合法区间内。尤其是有嵌套 while 跳过某些元素比如跳过非字母字符时内层 while 一定要加left right条件否则可能访问越界。指针连续跳跃多步时每跳一步都要重新检查边界。三数之和里的去重 while就是典型的多步跳跃场景漏掉边界条件直接报 IndexError。调试三板斧是我实际排错时最依赖的手段打印每一步的 left、right 和当前位置的值。很多看起来逻辑对但结果错的题一打印就发现指针移动方向和预期相反。用极小数据集做测试空数组、单元素数组、全相同元素数组、已经排好序的数组。这四个用例能覆盖 90% 的边界问题。手动模拟一遍指针移动导致的候选集收缩。在纸上画一条数轴把 left 和 right 每次移动后划掉的候选组合区域标出来能直观看出移动是否合理。5. 面试实战闭环从会做到会讲5.1 五步讲题法双指针题目在面试里考验的往往不只是写代码还有你能不能把思路讲清楚。我给准备面试的朋友推荐一个五步讲题法澄清输入和约束。数组是否有序能否排序能否用额外空间这两个问题决定了双指针可不可用。先给暴力解。明确说出暴力是 O(n²)我们可以优化让面试官看到你有复杂度意识。提出双指针并讲正确性依据。重点说因为数组有序指针移动后哪些组合被排除所以不会漏答案。边写边讲边界处理。循环条件为什么是指针移动为什么是这一侧去重为什么在这里做。跑一个例子并给复杂度。手动模拟 3-4 步然后说出时间 O(n)、空间 O(1)。第 3 步是最容易被忽视的。很多人一上来就写双指针但被问到你的算法为什么是正确的就卡住。提前把每次移动淘汰哪些组合想清楚这个问题就迎刃而解。5.2 复杂度与正确性的表达话术双指针的复杂度分析其实很简单但我见过很多人说得含糊。正确的说法是两个指针各自最多移动 n 次或整个数组长度每次循环至少移动一个所以总操作次数不超过 2n时间复杂度 O(n)空间复杂度 O(1)——除了排序的预处理比如三数之和需要先排序总复杂度是 O(n log n)。如果面试官追问为什么不是 O(n²)可以用收窄扫描的说法每个指针只会单向移动不会回头所以每个元素最多被访问常数次。5.3 高频变体题清单与练习顺序最后给一份我整理的高频双指针题清单按练习顺序排题目编号对应力扣题号其他平台一般也是同一批题阶段题目类型入门344 反转字符串、125 验证回文串相向双指针基础核心167 两数之和 II、15 三数之和、11 盛最多水的容器相向双指针高频进阶42 接雨水相向双指针 左右最大值维护入门26 删除有序数组重复项、27 移除元素、283 移动零同向快慢指针链表141 环形链表、142 环形链表 II、876 链表的中间节点同向快慢指针数组88 合并两个有序数组逆向双指针滑动窗口3 无重复字符最长子串、76 最小覆盖子串同向双指针变体练习顺序建议先把 344 和 125 这种最基础的写了找手感然后集中刷相向双指针的 167/15/11理解为什么移动指针是安全的再切到同向双指针的 26/27/283感受快慢指针最后上链表和滑动窗口这时候你会发现双指针的框架已经内化了——看到一个新题你第一反应不是去背哪个模板而是去分析两个指针各自移动到什么位置会排除哪些可能性。我自己的体会是双指针最核心的不是代码模板而是那个淘汰候选集的心智模型。当你拿到一道题能在脑子里画出两个指针在数组上游走、每移动一步就划掉一片区域的画面时双指针对你来说就不再是一个需要背的标签而是一种条件反射了。最后分享一个小技巧刷双指针题的时候故意把每个题的暴力解也在纸上写一遍然后对着暴力解问自己——哪部分计算是重复的、哪部分组合在逻辑上不可能成为答案。能把这个问题回答清楚双指针题你基本就过关了。
双指针算法面试通关指南：从暴力优化到边界处理
如果你正在准备算法面试随便打开哪个刷题平台的高频题单“双指针”三个字一定是绕不开的常客。热词榜上它长期霸榜不是没道理——几乎所有主流面试题库里双指针标签下的题目数量都排在前面而且这个技巧本身也足够优雅不需要复杂的数据结构只要两个游标就能把一堆 O(n²) 的暴力解压到 O(n)。这篇文章不打算讲什么高深理论我想从一个刷题老手和面试官双重身份的角度把双指针这件事讲透它为什么高频、底层逻辑是什么、相向和同向两大门派怎么区分、五道必会高频题怎么拆解、以及我在实际刷题和面试里踩过的边界条件的坑。1. 双指针为什么是高频本质上是把搜索空间砍掉一大半1.1 暴力双循环的问题出在哪先看一个最经典的场景在有序数组里找两个数使它们的和等于 target。新手第一反应肯定是双重循环def two_sum_brute(nums, target): n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j] target: return [i, j] return []这段代码能跑但时间复杂度是 O(n²)。数组长度到 10⁵ 量级就是 10¹⁰ 次运算基本告别活路。问题的根源在于双重循环把每一对组合都枚举了一遍绝大多数组合根本不可能成为答案这些计算全部是浪费。面试官看到 O(n²) 的解法接下来的追问几乎是可以预判的能不能优化到 O(n) 而双指针就是回答这个问题的标准答案。1.2 指针移动的本质每次移动都淘汰一批不可能的组合双指针之所以能提速关键不在两个指针这个形式而在于有序性带来的淘汰逻辑。拿上面的例子说假设数组是升序的left 指向左端right 指向右端当前和nums[left] nums[right]小于 target。请问right 左侧的所有位置和 left 组合还有可能等于 target 吗不可能。因为数组有序nums[right]是当前右指针位置最大的值相对右侧区间而言右边如果再往左走值只会更小和固定 left 加出来的和只会更小离 target 越来越远。所以以 left 为左端点的所有候选组合在这一瞬间可以整体划掉。每次移动指针淘汰的是一整块组合而不是一个单独的组合。left 最多移动 n 次right 也最多移动 n 次总共 O(n) 次操作就能覆盖所有可能的答案区间。这就是双指针的底层逻辑——利用数据的有序性或单调性让指针的每次移动都有排除法的意义。1.3 双指针的两大门派相向与同向我刷题时习惯把双指针分成两类分类标准非常简单两个指针的移动方向。相向双指针对撞指针left 从数组头部出发right 从尾部出发两者向中间靠拢。典型场景是排好序的数组、需要夹逼判断的场景比如两数之和、三数之和、盛最多水的容器、回文串判断。同向双指针快慢指针/滑动窗口两个指针从同一端出发一个走得快一个走得慢或者一个负责扩展一个负责收缩。典型场景是原地去重、链表判环、连续子数组/子串问题滑动窗口本质也是同向双指针。这两类的判断方法我后面会展开讲。先说结论看到有序数组 求和/比较类题目优先想相向看到子数组、子串、链表环类题目优先想同向。2. 相向双指针两边夹逼的核心套路与三道高频题2.1 两数之和 II输入有序数组最标准的对撞模板力扣 167 是相向双指针的入门第一题也几乎是所有面试官检验你双指针基本功的第一题。完整解法def two_sum(numbers, target): left, right 0, len(numbers) - 1 while left right: current numbers[left] numbers[right] if current target: return [left 1, right 1] # 题目要求从 1 开始计数 elif current target: left 1 else: right - 1 return []整个循环的核心逻辑只有三行和太小就左边往右走和太大就右边往左走相等就返回。为什么这么移动是安全的刚才已经解释过了——有序数组里left 固定时right 往左走和只会变小反过来right 固定时left 往右走和只会变大。每走一步就排除掉一整片不可能的区域。很多人会忽略两个小细节。第一是循环条件left right不是因为两个指针不能指向同一个元素题目要两个不同的数。第二是返回下标是从 1 开始数的很多人刷的时候直接用原数组下标一提交就挂。2.2 三数之和排序 夹逼 去重的综合考验力扣 15 是面试里真正的分水岭。能写出两数之和的人很多但三数之和能把一大批人挡在门外核心难点是全去重。思路本身不复杂先排序固定一个数nums[i]然后在i1到数组末尾这段区间上跑两数之和用相向双指针。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 # 剪枝nums[i] 已经大于 0后面的数都更大不可能凑成 0 if nums[i] 0: break 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]]) left 1 right - 1 # 二层去重跳过重复的 left 和 right while left right and nums[left] nums[left - 1]: left 1 while left right and nums[right] nums[right 1]: right - 1 elif total 0: left 1 else: right - 1 return res我在这里踩过的坑是只做了第一层去重固定元素去重忘了在找到一个三元组之后对 left 和 right 去重。结果就是同一个三元组因为 left/right 的重复值反复出现提交直接超时或返回重复结果。第一次因为这个问题 debug 了半小时后来长记性了——去重一定是在找到结果之后立刻做而且要连跳两次。nums[i] 0直接 break 是个很好的剪枝技巧排序之后数组是升序的固定元素都大于 0 了后面所有数都不可能把和拉回 0再往后更不可能。这种剪枝在面试里主动提出来很加分。2.3 盛最多水的容器为什么永远只移动较短的那条边力扣 11 的表面形式是求面积但解法依然是相向双指针。这题最反直觉的地方在于两个指针一个指向左墙一个指向右墙面积 短边高度 × 宽度。每次到底该移动哪边直觉上很多新手会想移动长边试试因为长边高挪一下说不定遇到更高的。错。正确的策略是永远移动短边。证明其实很简单假设height[left] height[right]当前面积 height[left] * (right - left)。如果我们固定 left 不动把 right 往左移宽度必然变小而高度被短边height[left]死死压住——即使遇到的墙再高容器高度还是height[left]。所以所有left 不动、right 左移的组合面积都不可能超过当前值。唯一有机会让面积变大的是把 left 往右移去寻找一条更高的短边。def max_area(height): left, right 0, len(height) - 1 ans 0 while left right: area min(height[left], height[right]) * (right - left) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ans这题的时间复杂度同样是 O(n)空间 O(1)。面试官追问为什么移动短边是对的时能把这个短边限制高度移动短边才可能提升高度的论证讲清楚比背代码有用得多。3. 同向双指针快慢指针与滑动窗口的统一视角3.1 删除有序数组中的重复项快慢指针最基本的形态力扣 26 是我认为理解同向双指针最好的入手题。题目要求原地修改数组不能新建额外空间。解法是用一个 slow 指针维护已处理好的无重复前缀的末尾用一个 fast 指针扫描整个数组。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这里的不变量是nums[0..slow]始终是已处理部分中不含重复的序列。fast 每遇到一个新值就把它搬到 slow 的下一个位置。整个过程 fast 走一遍slow 跟着走两个指针同向运动快的负责探索慢的负责记录。这种快指针探路、慢指针写结果的模式在力扣 283 移动零、力扣 27 移除元素里几乎一模一样学会一道相当于会了三道。3.2 环形链表检测Floyd 判圈从追及理解快慢指针链表的快慢指针和数组略有不同但思想一脉相承。力扣 141 判断链表是否有环经典解法是龟兔赛跑——slow 每次走一步fast 每次走两步如果链表有环快指针最终会从后面追上慢指针。def has_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False为什么快指针走两步而不是三步其实走三步也能追上但步长差得越多编码时的空指针判断越麻烦。最稳的是步长差 1在环上fast 相对于 slow 的速度是 1 步/轮无论环多长追及过程都能保证在有限轮内相遇。如果步长差不是 1在某些环长组合下可能会跳过相遇点需要额外的数学处理得不偿失。这题的进阶版力扣 142要返回环的入口节点解法是在快慢指针相遇后把一个指针重置回 head两个指针各走一步再次相遇的位置就是入口。这个结论很多资料直接给了但面试时最好能说出理由相遇点到入口的距离 head 到入口的距离。能讲清楚这点的候选人基本是真正理解了 Floyd 判圈而不仅仅是背模板。3.3 合并两个有序数组从后往前的逆向双指针力扣 88 是一个很有意思的反例它用双指针但方向是从尾部往头部走。题目给了两个有序数组 nums1 和 nums2nums1 长度是 mn后面 n 个位置是空的要求把 nums2 合并进 nums1。如果从前往后合并nums1 的原元素会被覆盖掉因为有效的 m 个元素塞不满 mn 个位置从前填会先动前面的位置。所以正确做法是从后往前填def merge(nums1, m, nums2, n): i, j, k m - 1, n - 1, m n - 1 while i 0 and j 0: if nums1[i] nums2[j]: nums1[k] nums1[i] i - 1 else: nums1[k] nums2[j] j - 1 k - 1 # nums1 的前 m 个如果有剩余已经在正确位置只需处理 nums2 剩余 while j 0: nums1[k] nums2[j] j - 1 k - 1这也是双指针只不过夹逼的对象是数组的尾部和尾部移动方向从外向里变成从后往前。它提醒我一件事双指针的方向不是只有左到右和两端往中间要结合数据存储的位置灵活调整。面试中遇到原地合并这类题先想想哪个方向的覆盖不会丢数据。3.4 滑动窗口同向双指针的变体滑动窗口本质上是同向双指针right 指针负责扩张窗口left 指针负责在条件不满足时收缩窗口。以力扣 3 最长无重复字符子串为例def length_of_longest_substring(s): 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核心逻辑是right 扩展到一个新字符时如果它已经在窗口里说明重复了就不断移动 left 把重复字符从窗口里挤出去直到窗口干净。每一步窗口[left, right]内的子串都是无重复的取所有窗口长度的最大值。复杂度看起来有嵌套 while但 left 最多移动 n 次整体还是 O(n)。我在实际面试里发现很多候选人能背出模板但说不清为什么 left 不需要回头。原因正是同向双指针的单调性窗口收缩之后left 只会继续往右不需要回到之前的位置重新扩张因为之前的子串已经处理过了。4. 边界条件与调试双指针翻车的高发区4.1 while 条件里的 与 到底差在哪这是双指针初学者最容易翻车的地方面试里也经常有人当场卡住。我的经验是分场景记处理元素对的场景两数之和、三数之和、回文串判断用left right。因为 left 和 right 指向同一个元素时这一对不合法。二分查找场景用left right因为查找的是单个位置mid 位置本身可能是答案不能把它排除在外。滑动窗口场景内层收缩用while left right或while left right都可能出现取决于窗口是否允许为空。比如找最短覆盖子串时窗口可以空就要允许 left 超过 right。一个很实用的检查方法写出循环体之后看看如果 left 和 right 刚好相邻、刚好相等、刚好交叉程序分别会怎么走。这三个状态测一遍边界问题基本能暴露出来。4.2 指针移动的时机什么时候只动一个什么时候一起动以两数之和为例子current target时只移动 leftcurrent target时只移动 right这是确定的。但在三数之和里找到total 0之后left 和 right必须同时移动否则会出现两种情况只移动 left 的话新的组合以当前 right 为右边界可能又凑出一个和为 0 的组合但你不知道是该继续还是该停更糟糕的是如果你忘了移动直接死循环。还有个容易忽略的场景在盛最多水的容器里如果height[left] height[right]两边高度相等移动哪边都行但必须至少移动一个而且最好一次性跳过所有与当前边等高的位置这样能少算很多无意义的面积。我刷题时习惯写成if height[left] height[right]移动 left虽然另一侧的等值情况没被优化但不会出错。4.3 三条铁律 调试三板斧踩过足够多的坑之后我自己总结出双指针代码的三条铁律每次循环迭代至少有一个指针发生移动。这是终止性的保证。如果某条分支没有移动指针八成就是死循环的开始。在访问nums[left]或nums[right]之前确认指针还在合法区间内。尤其是有嵌套 while 跳过某些元素比如跳过非字母字符时内层 while 一定要加left right条件否则可能访问越界。指针连续跳跃多步时每跳一步都要重新检查边界。三数之和里的去重 while就是典型的多步跳跃场景漏掉边界条件直接报 IndexError。调试三板斧是我实际排错时最依赖的手段打印每一步的 left、right 和当前位置的值。很多看起来逻辑对但结果错的题一打印就发现指针移动方向和预期相反。用极小数据集做测试空数组、单元素数组、全相同元素数组、已经排好序的数组。这四个用例能覆盖 90% 的边界问题。手动模拟一遍指针移动导致的候选集收缩。在纸上画一条数轴把 left 和 right 每次移动后划掉的候选组合区域标出来能直观看出移动是否合理。5. 面试实战闭环从会做到会讲5.1 五步讲题法双指针题目在面试里考验的往往不只是写代码还有你能不能把思路讲清楚。我给准备面试的朋友推荐一个五步讲题法澄清输入和约束。数组是否有序能否排序能否用额外空间这两个问题决定了双指针可不可用。先给暴力解。明确说出暴力是 O(n²)我们可以优化让面试官看到你有复杂度意识。提出双指针并讲正确性依据。重点说因为数组有序指针移动后哪些组合被排除所以不会漏答案。边写边讲边界处理。循环条件为什么是指针移动为什么是这一侧去重为什么在这里做。跑一个例子并给复杂度。手动模拟 3-4 步然后说出时间 O(n)、空间 O(1)。第 3 步是最容易被忽视的。很多人一上来就写双指针但被问到你的算法为什么是正确的就卡住。提前把每次移动淘汰哪些组合想清楚这个问题就迎刃而解。5.2 复杂度与正确性的表达话术双指针的复杂度分析其实很简单但我见过很多人说得含糊。正确的说法是两个指针各自最多移动 n 次或整个数组长度每次循环至少移动一个所以总操作次数不超过 2n时间复杂度 O(n)空间复杂度 O(1)——除了排序的预处理比如三数之和需要先排序总复杂度是 O(n log n)。如果面试官追问为什么不是 O(n²)可以用收窄扫描的说法每个指针只会单向移动不会回头所以每个元素最多被访问常数次。5.3 高频变体题清单与练习顺序最后给一份我整理的高频双指针题清单按练习顺序排题目编号对应力扣题号其他平台一般也是同一批题阶段题目类型入门344 反转字符串、125 验证回文串相向双指针基础核心167 两数之和 II、15 三数之和、11 盛最多水的容器相向双指针高频进阶42 接雨水相向双指针 左右最大值维护入门26 删除有序数组重复项、27 移除元素、283 移动零同向快慢指针链表141 环形链表、142 环形链表 II、876 链表的中间节点同向快慢指针数组88 合并两个有序数组逆向双指针滑动窗口3 无重复字符最长子串、76 最小覆盖子串同向双指针变体练习顺序建议先把 344 和 125 这种最基础的写了找手感然后集中刷相向双指针的 167/15/11理解为什么移动指针是安全的再切到同向双指针的 26/27/283感受快慢指针最后上链表和滑动窗口这时候你会发现双指针的框架已经内化了——看到一个新题你第一反应不是去背哪个模板而是去分析两个指针各自移动到什么位置会排除哪些可能性。我自己的体会是双指针最核心的不是代码模板而是那个淘汰候选集的心智模型。当你拿到一道题能在脑子里画出两个指针在数组上游走、每移动一步就划掉一片区域的画面时双指针对你来说就不再是一个需要背的标签而是一种条件反射了。最后分享一个小技巧刷双指针题的时候故意把每个题的暴力解也在纸上写一遍然后对着暴力解问自己——哪部分计算是重复的、哪部分组合在逻辑上不可能成为答案。能把这个问题回答清楚双指针题你基本就过关了。
