1. 专题二在练什么双指针的两大套路和适用前提1.1 双指针的本质是剪枝而非枚举双指针算法写进第二个专题目标就不一样了。入门的时候我们聊的是套路左右往中间夹、一个快一个慢绕圈、前后拉开距离。但到了刷题和面试实战题目不会好心地告诉你这题用双指针你得从排序、去重、窗口、面积、子数组这些概念背后把线索拎出来。这篇笔记就用五道高频题把双指针的识别方法、证明思路、边界处理完整过一遍适合已经能看懂基础双指针代码、但自己一做题就卡住的朋友。先说一个容易误解的地方双指针看起来是在枚举两个位置实际上它是在做剪枝。暴力解法是把所有位置组合都试一遍双指针则根据单调性每次移动指针时排除掉一整批不可能成为答案的情况。拿有序数组里找两数之和来举例。左指针在最左右指针在最右如果当前和太大说明右指针太靠右right 往左挪一位。这个操作看起来只是挪了一个指针但它同时排除了当前这个右指针和左边所有剩余左指针的配对。因为它们都比当前左指针的值更大或相等和只会更大不可能等于目标值。一次移动干掉一片组合这就是剪枝。专题二里的题目都是这种思路的延伸。三数之和是在两层固定之上借用左右指针把 O(n^3) 砍到 O(n^2)接雨水和盛最多水的容器是靠左右指针的收缩顺序来保证每个位置只会被处理一次滑动窗口则是在右指针扩、左指针缩的过程中让每个元素最多进出窗口一次。看起来形态不同底层逻辑都是同一句话利用数组的单调性大量剪掉无效枚举。1.2 三个前置特征帮你认出双指针题很多朋友问我怎么判断一道题能不能用双指针。我的经验是看三个特征命中其中一个就有戏。第一个特征是数据有单调性。这里的单调性不一定是严格递增也可以是有序数组、某个前缀和的性质、或者接雨水问题里最左和最有边界必然存在一个兜底墙这样的逻辑。双指针的正确性基本都建立在单调性上没有单调性移动指针就没有依据。第二个特征是问题在两个端点上做文章。比如盛最多水的容器面积由左右两个柱子决定接雨水每个位置的水位看左右两边的最大值三数之和固定一个数后剩下两个数在一段区间里夹逼。只要题目可以抽象成两个端点在一条线上移动双指针就大概率有戏。第三个特征是暴力解法的复杂度是平方或更高。O(n^2) 往往意味着你在枚举所有二元组O(n^3) 意味着三重循环。双指针最擅长的事情就是把这些枚举降到 O(n) 或 O(n^2) 里的内层线性扫描。所以看到一个题目暴力解法写了三层循环不用急着放弃先想一想能不能排序能不能固定一部分剩下的部分用两个指针滑动。当然这三个特征只是识别信号真正要落地还得看具体实现。接下来用五道题把识别 证明 去重 边界这四件事一次讲透。2. 五道必刷题拆解从暴力复杂度到双指针最优解2.1 三数之和排序 左右夹逼 去重O(n^2)题目本身很经典给定一个整数数组 nums找出所有不重复的和为 0 的三元组。暴力解法是三层循环O(n^3)而且去重非常痛苦因为它需要对三个位置同时做集合判重。更聪明的做法是先排序。排序之后固定第一个数 nums[i]那么问题就变成了在 i 后面的区间里找一个两数之和等于 -nums[i] 的配对。因为区间有序可以用 left 和 right 两个指针从两端夹逼。def threeSum(nums): nums.sort() n len(nums) res [] for i in range(n - 2): # 剪枝当前数已经大于0后面全是正数不可能凑出0 if nums[i] 0: break # 固定位去重跳过重复的 nums[i] 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有两个去重细节特别容易写错。固定位去重要用nums[i] nums[i - 1]而不是nums[i] nums[i 1]。用后面的那个比较会直接把下一个位置当作可能的 left 起点跳过导致漏解。用和前一个比较才是跳过重复的起点保留第一次出现的那个 i。命中答案之后left 和 right 都要跳跃到不同的值上然后再各挪一步。如果只挪一步下一次循环还会遇到相同的 left 和 right又凑出一组重复答案。这个忘记跳重的 bug 非常隐蔽因为部分样例能过但遇到 [0,0,0,0] 这种数组就会输出四组一样的答案。整体复杂度是 O(n^2)外层固定 i 是 O(n)内层 left/right 扫描是 O(n)排序的 O(n log n) 被内层主导。还有一个可选剪枝。固定 i 时可以算一下当前区间最小三数和nums[i] nums[i1] nums[i2]如果已经大于 0直接 break最大三数和nums[i] nums[n-2] nums[n-1]如果小于 0说明当前 i 太小continue 到下一个 i。这两个优化在某些极端用例里能把时间砍掉接近一半不会改变复杂度但值得写在代码里。2.2 接雨水左右指针的结算时机O(n)接雨水也是被讲烂了的高频题给定 n 个非负整数表示高度图每个柱子的宽度为 1计算下雨之后能接多少雨水。暴力解法很简单对每个位置分别找左边最高柱子和右边最高柱子取两者的较小值减去当前高度累加即可。这个做法是 O(n^2)。优化版可以先预处理 leftMax 和 rightMax 数组变成 O(n) 时间、O(n) 空间。双指针解法能把这个空间省掉降到 O(1)。def trap(height): left, right 0, len(height) - 1 left_max right_max 0 ans 0 while left right: left_max max(left_max, height[left]) right_max max(right_max, height[right]) if left_max right_max: ans left_max - height[left] left 1 else: ans right_max - height[right] right - 1 return ans关键问题是为什么当 left_max 小于 right_max 时可以立刻结算 left 这个位置的雨水量原因是当前这个位置能接的水取决于左侧最高值和右侧最高值中较小的那个。left_max 已经是左半边已知的最大值right_max 是 right 到数组末尾这段已知的最大值。如果 left_max 更小那么 for left 这个位置右侧一定存在至少 right_max 这么高的墙而 right_max 比 left_max 还高所以水位被 left_max 锁死。换句话说一个矮的 left_max 不用担心右边没有更高的墙兜底因为右边已知的最高墙已经比它高了。于是left_max - height[left]就是该位置的准确雨水量计算完可以直接 left。这里顺便说一个很多题解里容易让人绕晕的点网上有些版本比较的是height[left]和height[right]也能通过但解释起来非常绕。我推荐比较 left_max 和 right_max因为它的证明就是一句话水由矮的那一侧决定谁矮结算谁。面试时把这个思路讲清楚比背一个高度小的那边就是当前安全侧的结论要稳得多。这个解法的时间复杂度是 O(n)因为 left 和 right 总共把数组扫了一遍每个位置只被结算一次。需要额外注意边界如果 height 数组为空直接返回 0循环条件是left right写成会越界访问。2.3 盛最多水的容器短板贪心的证明O(n)很多人在接雨水之后接着刷这道题会误以为思路完全一样其实两者有本质区别。接雨水是累加每个柱子上的水量盛最多水的容器是求两条线之间能围成的最大面积min(height[l], height[r]) * (r - l)。面积不是累加出来的而是取一对左右边界算一个值再不断更新最大值。暴力解法同样是 O(n^2)。双指针解法很简洁。def maxArea(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为什么每次移动较矮的那一边就一定不会错过最大面积这个证明值得记住。假设height[left] height[right]当前面积为height[left] * (right - left)。如果移动的是 right也就是让右指针往左走一步那么新的宽度一定更小而且新的面积里min(height[left], height[new_right])一定不会超过height[left]。矮板不换高板往里缩宽度变小高度不可能变大面积必然变小。所以任何时候移动高的一侧都是白费力气只有移动矮的一侧才有可能换上一个更高的新板子让面积有突破的机会。和接雨水做个对比就特别清晰接雨水移动矮的那一侧是因为矮侧的积水可以结算了盛水容器移动矮的那一侧是因为矮侧继续作为边界没有潜力了。一道题是结算、一道题是淘汰动作一样理由完全不同。这个解法同样 O(n)。代码里不需要额外去重因为找的是最大面积允许使用任意一对柱子重复值不影响答案。我见过有人在这题里加一堆判断去重属于不必要的复杂度。2.4 无重复字符的最长子串滑动窗口 哈希表O(n)上面三题都是左右指针从两端往中间走滑动窗口则是另一种形态左右指针都从一个方向出发右指针负责扩大窗口左指针负责收缩窗口。题目要求给定一个字符串 s找出其中不含有重复字符的最长子串的长度。暴力解法枚举所有子串检查每个子串是否有重复字符O(n^3) 起步。滑动窗口的做法是维护一个窗口窗口里的字符保证互不相同右指针不断向右扩展一旦发现重复左指针就收缩到没有重复为止。def lengthOfLongestSubstring(s): window set() left 0 ans 0 for right in range(len(s)): while s[right] in window: window.remove(s[left]) left 1 window.add(s[right]) ans max(ans, right - left 1) return ans这个写法最好懂但还有一个更省常数的版本用字典记录每个字符最近出现的位置左指针可以直接跳过去不需要 while 一点点挪。def lengthOfLongestSubstring(s): last {} left 0 ans 0 for right, ch in enumerate(s): if ch in last and last[ch] left: left last[ch] 1 last[ch] right ans max(ans, right - left 1) return ans这里有一个细节经常被忽略判断last[ch] left是必须的。因为字典里可能存着这个字符非常古老的出现位置它已经在窗口之外了。如果不加这个判断left 可能会被拉回一个比当前窗口更早的位置导致窗口里重新混入重复字符。两个版本都是 O(n)差别只在常数。第一种写法每个字符最多进一次窗口、出一次窗口严格 O(n)第二种写法右指针每次扩展一步左指针最多可能跳跃多次但总体也是 O(n)。面试时先写第一种时间充足再优化成第二种反而能展示思路层次。2.5 长度最小的子数组窗口收缩的单调性前提O(n)这道题是滑动窗口在数组场景下的标准练习给定一个正整数数组 nums 和一个正整数 target找出 nums 中满足其和大于等于 target 的最短连续子数组的长度如果不存在则返回 0。滑动窗口的写法非常固定右指针负责扩张把新的数加入窗口总和一旦总和满足条件就尝试左指针收缩一边收缩一边更新最小长度直到总和不再满足条件。def minSubArrayLen(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 ans if ans ! float(inf) else 0这个题有一个非常重要的前提数组元素必须全部为正。为什么因为滑动窗口的收缩逻辑依赖单调性。右指针向右扩展时窗口总和一定变大左指针向右收缩时窗口总和一定变小。一旦数组里出现负数窗口总和就不再单调总和变小可能不是因为收缩窗口而是因为遇到了一个很大的负数这种情况下 while 收缩的判断就完全失效了。如果题目改成数组可能包含负数只能用前缀和加有序数据结构比如二分或者 Fenwick 树来做。我在面试里问过不少人很多能流畅写出滑动窗口版本但一问这题为什么要求正整数就卡住。这个点一定要能解释清楚。3. 双指针的三种形态和多指针变体什么时候用哪一把3.1 左右相向指针适合在一段区间里找配对/算极值的题左右相向指针是所有双指针里最经典的形态left 从数组开头right 从数组结尾两只指针往中间靠。使用场景一般是两个特征一是区间本身或经过排序后具有单调性二是问题的答案与两个端点同时相关。典型题目除了上面说的三数之和、接雨水、盛最多水的容器还有有序数组的两数之和、判断回文串、翻转数组元素。解题时需要考虑的是每次移动哪只指针以及移动的依据是什么。这个依据可以来自数学推导比如盛水容器的移动矮板才有潜力也可以来自当前结果和目标的关系比如三数之和里总和小于 0 就 left 右移。做这类题最容易犯的错误是凭直觉移动指针。我见过一个候选人做两数之和变体当前和小于 target 时他说我觉得应该移动右指针因为右边数大这完全反了。移动的依据不是数的大小而是当前结果和目标的关系。总和小于目标说明需要更大的数右指针已经是最大的数之一往左只会更小所以必须左指针向右挪。移动指针前先自己在心里推一遍这次移动排除了哪些组合为什么这些组合不可能是答案想通了再写代码。3.2 快慢指针适合链表和原地数组操作的题快慢指针的经典战场是链表fast 一次走两步slow 一次走一步用来检测链表中是否有环、寻找链表中间节点、寻找链表倒数第 k 个节点。数组场景里也有变体比如删除有序数组中的重复项slow 指向要被覆盖的位置fast 负责探索新值。def removeDuplicates(nums): slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 1快慢指针的核心思路是制造速度差让两个指针在同一个结构上处于不同的进度。链表的题特别要注意 fast 移动时判空否则容易在链表末尾报空指针异常数组的题则要区分覆盖写入和交换两种模式覆盖写入时 slow 是最终结果的下标交换时两个指针对应不同的语义。3.3 滑动窗口适合连续子串/子数组的问题滑动窗口和左右相向指针最大的区别是方向两个指针都从左往右移动右指针扩张左指针收缩窗口始终维护一个合法的连续区间。适用场景很明确题目是求连续子串或子数组的某个性质比如最长无重复子串、最小覆盖子串、和为目标的连续子数组。固定窗口大小和可变窗口大小是两种套路。固定窗口通常是先让右指针走到窗口大小然后右移一步、左移一步保持窗口宽度不变可变窗口则是右指针不断扩张左指针根据条件收缩。写滑动窗口时要先想清楚一个问题什么时候收缩收缩到什么时候停止。这决定了 while 还是 if。比如无重复字符的子串遇到重复字符就需要一直挪到没有重复为止所以是 while而字符串排列这种题目窗口大小固定左指针跟着右指针一起移动一次用 if 就够了。滑动窗口里另一个高频坑是元素离开窗口时没有从状态里移除。窗口维护的统计结构不管是 set、哈希表还是计数数组都必须保持当前窗口的准确状态。右指针加入一个元素要更新状态左指针移除一个元素同样要更新状态少一个都会导致判断错误。3.4 三指针变体颜色分类与四数之和双指针再往前走一步就是三指针。最典型的题目是颜色分类数组里只有 0、1、2 三种值要求原地排序。这个问题用两个边界指针加一个遍历指针解决。def sortColors(nums): p0, p2 0, len(nums) - 1 i 0 while i p2: if nums[i] 0: nums[i], nums[p0] nums[p0], nums[i] p0 1 i 1 elif nums[i] 2: nums[i], nums[p2] nums[p2], nums[i] p2 - 1 # 这里 i 不前进因为交换回来的值还需要检查 else: i 1三个指针各自负责一件事p0 维护 0 的区间的右边界p2 维护 2 的区间的左边界i 负责遍历中间未处理区域。当 nums[i] 是 2 时交换之后不能立刻 i因为换回来的可能是 0 也可能是另一个 2需要留在原地继续判断当 nums[i] 是 0 时换回来的只可能是 1因为 p0 指向的位置已经被 i 扫描过且不是 2所以可以直接前进。这个细节就是三指针题的灵魂。三数之和之后还有四数之和。思路是一层一层固定外层数字内层再用双指针。排序之后外层依次固定 a 和 b内层 left 和 right 在剩下的区间夹逼去重逻辑也要应用在四个位置上。整体复杂度 O(n^3)。写多指针题有个通用技巧先把循环变量分清楚固定哪些、遍历哪些、移动哪些一字排开再动手。三指针尤其容易在交换条件里搞混移动顺序建议在草稿纸上画出三块区域和指针位置再写代码。4. 高频考点速查表把双指针题型的复杂度和关键点收进一张表4.1 速查表下面这张表是我自己刷题时整理的把双指针最常见的题型、指针形态、复杂度和核心考点放在一起方便面试前快速过一遍。题目指针形态时间复杂度核心考点两数之和有序数组左右相向O(n)单调性剪枝三数之和固定一维 左右相向O(n^2)排序 三层去重四数之和固定两维 左右相向O(n^3)多指针组合 去重接雨水左右相向O(n)结算时机与左右最大值盛最多水的容器左右相向O(n)短板贪心证明判断回文串左右相向O(n)字符比较 边界删除有序数组中的重复项快慢同向O(n)覆盖写入链表中环的检测快慢同向O(n)速度差无重复字符的最长子串滑动窗口O(n)窗口内状态维护长度最小的子数组滑动窗口O(n)收缩单调性前提最小覆盖子串滑动窗口 哈希计数O(n)窗口状态精确维护颜色分类三指针O(n)原地交换 换回值判断这张表的价值不在于背代码而在于快速回忆每个题型的题眼。比如看到最小覆盖子串第一反应就是维护两个哈希表或者一个计数数组右指针扩张补字符左指针收缩删字符再配合 need 和 have 两个计数器判断是否已经覆盖。把关键步骤钉在脑子里比临场推导省事得多。4.2 怎么按表制定练习节奏如果你还在刷题阶段我建议不要按题目难度递增来练这张表而是按指针形态分组练。第一组先练左右相向两数之和、判断回文串、三数之和把夹逼和去重手感练出来。第二组练滑动窗口无重复字符的最长子串、长度最小的子数组、最小覆盖子串重点体会窗口内状态怎么维护。第三组练快慢指针尤其是链表题把边界判空练成肌肉记忆。最后一组再接触三指针和四数之和因为前面的基础不牢多指针非常容易绕晕。每个组练习的节奏是先不看答案自己写写不出来也没关系看懂了之后关掉答案默写一遍然后再换一个新题验证。我见过很多人一种题型刷了二三十道还是记不住。原因很简单只刷不总结每一题都是孤立的。每做完一组题花十分钟把这一组题的指针移动依据和去重/边界细节写在本子上比多刷五题有用得多。5. 双指针最容易踩的坑和排查口诀5.1 四个高频实战坑第一个坑是排序后丢失下标。两数之和的原题要求返回下标就不能先排序再用双指针因为排序会打乱下标信息必须用哈希表。但两数之和的加强版题目说明数组已经有序这时双指针才是首选。三数之和、四数之和这类题目要求返回的是数值组合而不是下标排序完全没有问题。做题前先确认返回值到底依赖不依赖原始下标这个判断错了方向就全错了。第二个坑是去重时比较对象选错。三数之和里固定位去重要写nums[i] nums[i - 1]命中答案后左右指针要用 while 循环跳过重复值。去重比较的常见错误是写了nums[i] nums[i 1]这会把第一次出现的合法三元组也跳掉导致漏解。去重的一个更通用的原则是对于有序数组跳过连续相等的一整段但是永远要保留每段相等的第一个。第三个坑是命中答案之后忘记移动指针。很多人在 total 0 的分支里只 append 结果没有移动 left 和 right于是下一次循环又计算同样的组合陷入死循环。解决方法是命中后先把左右两边重复的跳过然后 left 和 right 各走一步。这是三数之和和相关变体的经典 bug排查时优先看这里。第四个坑是滑动窗口里状态更新不完整。窗口移动包括加元素和减元素两个动作加元素要更新统计状态减元素也要更新。比如无重复字符的最长子串移除窗口左端字符时必须同时从 set 里删掉如果只移动了 left 而没有更新集合下一次判断重复就会误判。排查这类问题的方法很简单把每一次窗口变化后的 set 或者哈希表内容打印出来和手推的对比一下就能发现。5.2 排查口诀与调试流程我自己的实战习惯是双指针代码写完先不急着提测按下面这套流程走一遍。第一步看边界。空数组、只有一个元素、所有元素都相同这三类用例先跑。双指针最常见的越界就发生在while left right这种写法上应改成left right。快慢指针在链表上还要额外判空。第二步看移动逻辑。逐个检查每个分支的指针移动方向确认移动的是应该移动的那一侧。接雨水里是谁矮移动谁盛水容器也是谁矮移动谁但理由完全不同别混。三数之和里是和小于 0 移 left和大于 0 移 right也别写成反过来。第三步看去重。把结果手动打印出来检查有没有重复三元组检查有没有漏掉边界上的合法组合。去重这个环节靠眼睛看比靠逻辑推理更有效。第四步看复杂度。确认循环内没有嵌套扫全数组的操作。滑动窗口虽然有两个 while但每个元素最多被 left 移出一次总复杂度仍然是 O(n)。如果发现复杂度不对多半是状态更新或者指针移动顺序出了问题。口诀可以总结成一句左移还是右移先问依据加元素还是减元素状态要同步去重去的是连续段保留第一个边界越界前先想 left 和 right 能不能相遇。排查问题的时候按这个顺序走基本能把 90% 的双指针 bug 消灭在提交之前。最后说一个我自己的习惯。拿到双指针的题不要急着写代码先在草稿纸上画一根轴把两个指针标出来然后问自己三个问题两个指针各自代表什么含义每一步要移动哪一个移动之后哪个信息被更新了这三个问题想清楚了代码基本不会跑偏。复杂的双指针题画图尤其重要三指针和四数之和这种不画图几乎不可能一遍写对。刷完这一专题你会发现双指针的题目其实就是一个不断做减法的过程每次移动指针都在告诉自己这一片组合已经不可能是答案了。想明白这一点算法题留给你的就不再是死记硬背而是一套可以迁移到任何场景的思考方式。