双指针算法全解析：从对撞、快慢指针到滑动窗口的LeetCode实战

一说到双指针很多人脑子里蹦出来的画面就是两个下标一个站在数组头一个站在数组尾往中间靠或者一个跑得快一个跑得慢。这个印象没有错但它把双指针想得太窄了。真正在 LeetCode 经典习题里出现的双指针问题很多都长着一张“完全不像双指针”的脸——有的要把数组想象成链表有的要用“排除法”证明移动指针的正确性有的甚至要先把“恰好K个”翻译成“最多K个”。这篇我会用 C 实现和大家一起拆掉“双指针两个指针扫一遍”这个思维框。我按“问题形态”而非“算法模板”来挑选题目LC 11盛最多水的容器、LC 42接雨水、LC 287寻找重复数、LC 992K 个不同整数的子数组再用 LC 15三数之和补一道排序后三指针的典型题。适合谁看一种是正在反复背模板但一换题就懵的人一种是笔试前想系统梳理双指针本质的人。整篇不会塞一堆冷门优化重点放在指针为什么这么移动、为什么移动完之后答案不丢、C 具体怎么写。1. 双指针的三个常见面孔以及一个被忽略的底层逻辑1.1 三种常规形态对撞、快慢、滑动窗口先花点篇幅把大家熟悉的三种形态摆出来后面才好说“不一样”在哪。左右对撞数组有序或者存在某种单调约束时使用left 从 0 向右、right 从 n-1 向左典型如两数之和 II、反转字符串、回文判断。每次移动哪一侧取决于当前计算结果和目标的比较。快慢指针多出现在链表或可抽象为链表的场景典型如链表判环、找链表中点、删除倒数第 N 个节点。它利用的是不同速度导致的路程差。滑动窗口本质上也是一个 left 和一个 right但两个指针同向移动窗口整体向右滑。典型如无重复字符的最长子串、最小覆盖子串、长度最小的子数组。这三种形态并没有覆盖全部双指针题。真正难的题往往是“形态”不明显或者要你把问题先做一层转化双指针才会出现。LC 287 就是一个典型表面是找数组里的重复数字实际上需要你用快慢指针去链表里找环。1.2 双指针的本质每次移动都是在排除候选解我自己的体会是双指针能成立的根本原因不是“它有俩指针所以厉害”而是在某个单调性条件下移动其中一侧指针后你可以确信有整整一片候选解永远不会成为最优解或答案于是放心地把它丢掉。以左右对撞为例指针每移动一步其实是在说“以当前位置作为左边界或右边界的所有可能性我已经算清楚了其中不可能诞生更好的答案。”这一步排除让 O(n²) 的搜索空间被压缩成 O(n)。这个“排除”的可靠程度是双指针题正确性证明的核心。后面 LC 11 和 LC 42 都会围绕这个逻辑展开。如果你发现自己在题解里看到双指针解法但完全无法理解“为什么可以这样移动”那通常不是代码问题而是缺了这个“排除”视角。带着这个问题去看下面几道题会比单纯背代码顺畅得多。2. LC 11 盛最多水的容器双指针靠“排除法”保证正确2.1 题目场景与暴力求解题目背景很直观给定一个长度为 n 的整数数组 heightheight[i] 表示竖立在 x 轴 i 位置上的柱子高度。选两个柱子它们与 x 轴围成的容器能装的水量 两个柱子中较矮的那个高度 × 两个柱子之间的距离。求最大水量。暴力做法是枚举所有左右边界组合计算面积取最大值复杂度 O(n²)。这题如果只会暴力笔试现场基本就慌了因为 n 可以到 1e5 级别。双指针做法长这样left 指向 0right 指向 n-1计算当前面积如果 height[left] height[right] 就 left否则 right--。每轮更新答案直到两指针相遇。代码量很少但真正值钱的是背后的证明。2.2 为什么移动“短板”一定不丢解假设当前 left 指着 aright 指着 b且 height[a] height[b]那么当前面积是 height[a] × (b - a)。此时把它和“所有以 a 为左边界、右边界在 a 和 b 之间的容器”比一比这些容器的宽度一定比 b-a 小这些容器的高度一定不会超过 height[a]因为 a 是短板不管右边换成谁短板要么还是 height[a]要么更矮。也就是说当左边界固定为 a 时当前这个容器已经是它能达到的最大面积。既然最大值已经拿到a 这个位置作为左边界的使命就结束了可以放心 left。反过来如果 height[a] height[b]同理b 作为右边界的使命结束right--。这就是前面说的“排除法”每轮移动的不是“较大的一侧”而是“已经不可能再贡献更大答案的那一侧”。这个证明简单可靠也恰恰是很多背模板的人忽略的本质。2.3 C 实现与复杂度分析class Solution { public: int maxArea(vectorint height) { int left 0, right (int)height.size() - 1; int ans 0; while (left right) { int h min(height[left], height[right]); int area h * (right - left); ans max(ans, area); if (height[left] height[right]) { left; } else { --right; } } return ans; } };等号情况怎么处理如果 height[left] height[right]移动哪边都行因为两边都已经是“使命结束”状态。代码里走了 else即移动 right不影响结果。复杂度 O(n)空间 O(1)。这里有一个容易被忽略的细节right 用 int 而不是 size_t否则 right-- 到 0 时可能因为无符号数溢出导致死循环。很多人在本地跑 size_t 版本会卡住问题就出在这。3. LC 42 接雨水双指针把 DP 数组省成了 O(1) 空间3.1 每个格子的水量公式接雨水的朴素思路是“逐格计算”对每个位置 i它能接的水 min(它左边所有柱子的最高值 leftMax[i]右边所有柱子的最高值 rightMax[i]) - height[i]。如果结果是负数按 0 记。为什么是这个公式因为一个格子能存水取决于左右两侧是否有更高的“墙”。水的高度上限是左右两侧最高墙里较低的那个再减去自身高度就是这一格能积的水。把所有格子的水量加起来就是答案。按公式直接做需要两个数组预处理 leftMax 和 rightMax时间复杂度 O(n)空间复杂度 O(n)。这在教材里是标准写法但面试官一般会追问一句能不能把空间优化到 O(1)3.2 从预处理数组到双指针收缩能。做法是让 left 从 0 往右、right 从 n-1 往左同时维护两个变量 leftMax 和 rightMax分别表示“已经扫过的左侧最大值”和“已经扫过的右侧最大值”。每次比较 leftMax 和 rightMax如果 leftMax rightMax说明当前 left 位置右侧的最大值至少不会低于 rightMax因此它的水量上限就是 leftMax直接让 ans leftMax - height[left]然后 left否则right 位置的水量上限就是 rightMaxans rightMax - height[right]然后 right--。这里的关键在于“哪边的最大值已经确定就先结算哪边”。leftMax 只更新左侧rightMax 只更新右侧两个变量足够因为它们已经覆盖了每侧扫过部分的最高墙。相比 DP 数组空间从 O(n) 降到 O(1)。3.3 C 实现和边界条件class Solution { public: int trap(vectorint height) { int n (int)height.size(); if (n 3) return 0; int left 0, right n - 1; int leftMax 0, rightMax 0; int ans 0; while (left right) { leftMax max(leftMax, height[left]); rightMax max(rightMax, height[right]); if (leftMax rightMax) { ans leftMax - height[left]; left; } else { ans rightMax - height[right]; --right; } } return ans; } };边界条件数组长度小于 3 时一定接不了水直接返回 0。leftMax 等于 rightMax 时走 else结算 right 侧不会漏算因为两侧最大值相等时随便结算哪边剩余格子的水量由另一边决定后面会继续结算。对比 DP 版本两个版本时间复杂度都是 O(n)但双指针版空间 O(1)。我建议初学的时候先把 DP 版写对再改成双指针版因为双指针这个“先结算确定侧”的思维一旦跳步很容易写出看似对、实则漏水的版本。我自己最开始写的就是每轮比较 height[left] 和 height[right] 而不是 leftMax 和 rightMax结果遇到某些非对称用例会差一点点调试了很久才意识到问题根源判断依据应该是“哪一侧的最大值已经确定”而不是“当前柱子的高度谁高谁低”。4. LC 287 寻找重复数数组当链表快慢指针用来找环4.1 题目约束与常规思路的死角题目人送外号“龟兔赛跑数组版”给定一个长度为 n1 的数组 nums里面的数字都在 [1, n] 范围内并且恰好有一个数字重复要求找出这个重复的数字。限制是不能修改数组不能排序只能用 O(1) 额外空间时间复杂度要低于 O(n²)。这几条限制直接把很多常规思路堵死了排序修改数组违规。用哈希集合额外空间 O(n)违规。暴力双层循环时间复杂度 O(n²)违规。那怎么办答案很“不一样”把这个数组看成一张隐式的链表。4.2 建立下标映射形成一个必然存在的环数组长度 n1元素范围 1..n意味着每个元素的值都落在合法下标范围内。于是可以从下标 0 出发把“某个下标 i”当作链表节点把 nums[i] 当作“该节点的 next 指针指向的下标”。例如 nums [1, 3, 4, 2, 2]从 0 出发0 - 1 - 3 - 2 - 4 - 2 - 4 - 2 ...走几步就会发现2 和 4 之间形成了一个环。为什么会形成环因为数组中有重复数字所以至少有两个不同的下标指向同一个 next 值于是链表里必然有环。环的入口就是那个重复的数字。把数组当链表快慢指针找环入口就是这题的完整思路。这里有个前提必须注意这个转化只对“值域 [1, n] 且长度为 n1”的数组有效。如果数组里有 0 或者有大于 n 的数直接把 nums[i] 当下标就可能越界。做题时一定要先看题目约束。4.3 快慢指针找环入口的 C 实现class Solution { public: int findDuplicate(vectorint nums) { int slow nums[0]; int fast nums[nums[0]]; while (slow ! fast) { slow nums[slow]; fast nums[nums[fast]]; } slow 0; while (slow ! fast) { slow nums[slow]; fast nums[fast]; } return slow; } };第一轮是“一步”和“两步”地跑直到快慢指针在环内相遇第二轮把一个指针重置到 0两个指针都以“一步”速度前进再次相遇的位置就是环入口。返回这个下标对应的数字即可。有人会问初始时 slow nums[0]、fast nums[nums[0]]为什么特殊因为要从 0 这个“哨兵节点”出发0 本身不会出现在值域里所以它不是环的一部分所有路径都从 0 开始走到环里。重置 slow 0 后再用经典的“链表找环入口”方法就好理解了。4.4 快慢指针为什么能保证找到重复值没有环的链表和“值都不同”是等价的一旦出现重复值等价于有两个节点指向同一个后继链表就分出环。快指针每次走两步慢指针走一步慢指针进环后最多走一圈多就会被快指针追上因此第一轮一定会相遇。第二轮的数学原理设环入口前有 a 步环周长 b 步第一轮相遇点距离环入口 c 步可以推导出 slow 重置后和 fast 同步走 a 步会在入口相遇。这个结论和判断链表环入口的结论一模一样只是把“节点”换成了“下标”。这类题的“不一样”在于它没有直接给你一条链表而是你主动把数组下标和值的对应关系解释成链表结构。双指针在这里不是用来扫数组而是用来在抽象的图上做追踪。我第一次见到时确实被惊艳到。5. LC 992 K 个不同整数的子数组“恰好”要拐个弯变成“至多”5.1 滑动窗口适合统计“至多”不适合直接统计“恰好”题目给一个正整数数组 A以及一个整数 K求有多少个连续子数组其中恰好有 K 个不同的整数。如果直接用一个滑动窗口去维护“恰好 K 种数字”会非常别扭。因为窗口扩张时不同整数数量会从一个值跳到另一个值窗口收缩时数量也可能一下子低于 K。你很难找到一个明确的收缩条件让窗口内恰好保持在 K 种。反过来如果问“最多有 K 个不同整数的子数组有多少个”滑动窗口就很好写right 不断向右扩展只要窗口里不同整数数量超过 K就移动 left 收缩窗口直到重新满足“最多 K 种”。每加入一个 right 后以 right 结尾的合法子数组数量正好是 right - left 1。这也是滑动窗口计数时的常用技巧。5.2 atMost(K) - atMost(K-1) 的数学依据“恰好 K 个不同整数” “最多 K 个不同整数 - 最多 K-1 个不同整数”。这个式子的逻辑很简单满足“最多 K 个”的子数组集合包含了不同整数个数为 1、2、...、K 的所有子数组满足“最多 K-1 个”的集合包含了 1、2、...、K-1 的所有子数组两个集合做差剩下的恰好是不同整数个数为 K 的子数组。所以把统计“恰好”转换成统计“至多”再写同一个 atMost 函数调用两次答案就有了。这是双指针滑动窗口题目里很典型的数学转化值得单独拿出来讲。5.3 C 实现与自测用例class Solution { public: int subarraysWithKDistinct(vectorint A, int K) { return atMost(A, K) - atMost(A, K - 1); } int atMost(vectorint A, int K) { if (K 0) return 0; unordered_mapint, int cnt; int left 0, res 0; for (int right 0; right (int)A.size(); right) { cnt[A[right]]; while ((int)cnt.size() K) { --cnt[A[left]]; if (cnt[A[left]] 0) { cnt.erase(A[left]); } left; } res right - left 1; } return res; } };可以自测一个简单例子A [1, 2, 1, 2, 3]K 2。肉眼数一下恰好有 2 个不同整数的子数组一共 7 个而调用 atMost(2) 得到 12atMost(1) 得到 5两者相减正好是 7。这个“两次 atMost”的思路本质上就是把一个不容易直接维护的边界条件拆成两个容易维护的边界条件再求差。理解这一点比记忆代码更有用。需要注意的是unordered_map 的 erase 在频繁增删时也有开销但这个题量级没问题。如果追求更极致可以用 vector 当计数器配合一个变量 kinds 记录当前不同数字数量这里就不展开了。6. 三数之和之外排序 双指针的去重陷阱6.1 为什么不先排序不行LC 15 三数之和找出数组里所有三元素组合使得三数之和等于 0。暴力的做法三重循环 O(n³)肯定不行。排序 双指针的标准解法本质上是在有序数组上做到 O(n²)。为什么必须先排序因为双指针的移动需要一个单调方向作为依据三个数固定一个 nums[i] 后剩下两个数 left 在 i1、right 在 n-1。如果 nums[left] nums[right] 比目标小说明 left 位置太小必须向右移动增大如果比目标大则 right 向左移动减小。有了排序移动方向才是确定的、不会回头的。这就是“有序性让双指针的排除法成立”的又一例子。6.2 三指针的移动规则和去重细节固定 i 作为第一个数left 和 right 分别从 i1 和 n-1 出发对撞。找到一组和为 0 后要把与当前 nums[left] 相同的所有元素跳过也要把与 nums[right] 相同的元素跳过否则同一个组合会被重复记录。外层 i 也一样如果 nums[i] 和 nums[i-1] 相等就跳过否则同一组三元组会重复出现。去重细节是这题最容易翻车的地方。很多人会写出“发现答案后只移动一边”的代码结果要么漏解要么重解。正确做法是发现答案后先把左右两侧所有重复值都跳过去再同时把 left、right--进入下一轮。为什么不能只移动一边因为当前组合已经满足条件只移动一边的话另一边还留在原值上三数之和要么偏大要么偏小而且很容易绕回重复组合。6.3 C 实现class Solution { public: vectorvectorint threeSum(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint ans; int n (int)nums.size(); for (int i 0; i n - 2; i) { if (nums[i] 0) break; if (i 0 nums[i] nums[i - 1]) continue; int left i 1, right n - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { ans.push_back({nums[i], nums[left], nums[right]}); while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) --right; left; --right; } else if (sum 0) { left; } else { --right; } } } return ans; } };如果 nums[i] 0因为数组已排序后面的数都更大三数之和不可能为 0可以直接 break。这是排序带来的额外剪枝。这个优化虽然小但在笔试里有提升。7. 一眼识别“隐藏的双指针题”我的判断口诀7.1 四个高频特征刷完上面几类题我总结出以下特征满足越多越值得尝试双指针数据对象是线性的数组或链表有一个“随移动单调变化”的性质比如高度可以累积成最大值、和可以随排序单调、不同数字数量可以随窗口收缩减少题目要求 O(1) 额外空间或者 O(n) 时间这两个限制会直接排除哈希表、DP 数组等方案你能找到一个尽量简化的候选区间然后每次移动指针都确信排除了一部分不可能的解。7.2 五道题的双指针形态对比题目指针形态核心思维LC 11 盛最多水的容器左右对撞移动短板用排除法剪枝LC 42 接雨水左右对撞比较两侧最大值先结算确定侧LC 287 寻找重复数数组上的快慢指针数组映射成链表找环入口LC 992 K个不同整数的子数组同向滑动窗口恰好转化为至多两次 atMostLC 15 三数之和排序后三指针排序 基准数 对撞 去重这几道看起来解法迥异但共同点都在于双指针只是表象真正关键的是“指针移动后有问题的候选解被稳定排除”。做题时不要急着写代码先问自己如果移动某一侧能排除哪些情况能证明排除后答案不丢吗能就可以写不能再想别的办法。7.3 三个容易踩的细节等号分支要有明确选择。LC 11 里高度相等时移动任意一边都可以LC 42 里两个最大值相等时建议统一走 elseLC 15 里去重循环一定要配合 left right 边界判断。无符号整数坑。left--、right-- 别忘了转 int尤其是在 size_t 与循环边界比较的时候。这类问题在本地跑没事一上线就是死循环或越界。指针移动要防数组越界。快慢指针里 fast nums[nums[fast]] 的前提是值域正好是合法下标滑动窗口里 while (cnt.size() K) 收缩时要注意 left 不能超过 right 1否则 res right - left 1 就成了负数。7.4 最后再分享个小技巧如果你想系统复习双指针不要按题号刷按我表格里的“指针形态”刷。每种形态挑 3 道题认真把正确性证明写一遍比盲目刷 50 道题有用得多。我个人的体会是见过再多模板都不如亲手推一遍“为什么可以移动指针”。推到能闭眼讲给另一个人听才算真正吃透。