1. 双指针专题为什么我先整理这一篇刷题这件事坚持一阵子之后我发现自己在笔记上犯了一个老毛病题目做了不少但过两周回来看除了题目编号和一句“已AC”什么都想不起来。于是从第一篇笔记开始我调整了记录方式——不再按题号顺序堆答案而是按“题型套路”归类每一类记录它的核心思想、适用信号、常用代码模板、以及我踩过的坑。这篇是第二篇笔记整理的是双指针Two Pointers专题也是我觉得性价比最高的一个模块。为什么双指针值得单独开一篇因为它在笔试和面试里出现频率极高而且往往藏在一些看起来和指针毫无关系的题目里。字符串反转、有序数组去重、链表环检测、滑动窗口、三数之和……这些题表面风格完全不同底层用的都是同一个思想用两个指针在数据结构上协同移动把时间复杂度从 O(n²) 降到 O(n)把空间复杂度从 O(n) 降到 O(1)。理解了这一层很多题就不需要背而是能“推”出来。这篇笔记适合三种人看刚开始刷题、想建立题型体系的新手刷了一两百道但总是似懂非懂、想打通套路的进阶者以及面试前想快速过一遍高频考点的求职者。代码我统一用 JavaScript 写因为前端岗笔试多用 JS而且 JS 写双指针的代码非常简洁便于看清逻辑主体。思路部分不依赖具体语言用其他语言的同学也能直接参考。2. 双指针的两种基础形态与识别信号2.1 左右指针从两端向中间夹逼左右指针是最直观的形态一个指向数据结构开头一个指向结尾按照某种条件向中间移动直到两个指针相遇。它的适用场景有几个很典型的信号数组或字符串是有序的或者可以排序题目要求找两个元素、判断是否存在某种组合题目涉及“区间”或“子串”的边界收缩。我印象最深的是“盛最多水的容器”那道题。实际上最早我拿它练手时第一反应是两层循环暴力枚举代码很快就写出来了但题目数据量一大就超时。后来才领悟到这类“两端夹逼”的问题每次移动指针时其实是在排除一个“不可能成为最优解”的候选这种排除思路才是双指针的灵魂。具体来说左右指针的通用模板是初始化 i 0、j len - 1在 i j 的循环里根据特定条件决定移动 i 还是移动 j循环结束后一般就得到了答案或者完成了一次处理。2.2 快慢指针一前一后不同速度快慢指针通常用于链表和数组原地操作。两个指针从同一起点出发但移动速度不同比如慢指针每次走一格快指针每次走两格或者一个先走、一个后走。它的识别信号也很清楚题目涉及链表中是否存在环、找链表中间节点、倒数第 K 个节点或者要求“原地”删除某类元素、去重不允许额外开数组。快慢指针最经典的场景是链表环形检测两个指针从头部出发慢指针每次一步、快指针每次两步如果链表有环它们一定会在环内相遇。这个结论我一开始觉得神奇但想通之后你会发现它本质上就是数学上的“追赶问题”——快指针相对慢指针以每步一格的相对速度前进如果存在环它一定能追上。另一个高频场景是数组原地操作比如移除指定值、删除有序数组重复项这类题用快指针遍历寻找“有价值”的元素慢指针负责记录“最终要保留”的位置。2.3 看到什么条件就想到双指针我整理了三个特别直观的识别信号刷题时命中任何一个都值得多往双指针方向想一想标签里同时出现“数组”“有序”“两数/三数”这类关键字的题链表类题目关心“位置”“环”“中点”而不是“值”的题题目限制条件里明确写了“原地 O(1) 空间”的题几乎可以默认在暗示指针操作不过要提醒一句双指针不是万能钥匙。如果数据本身无序且不能排序或者问题需要穷举所有子集、组合那多半还是得回到回溯或动态规划。识别边界本身就是经验的一部分做多了自然有感觉。3. 左右指针实战拆解三道题从入门到进阶3.1 基础题反转字符串的边界陷阱这道题是 LeetCode 第 344 题“反转字符串”要求原地修改字符数组空间复杂度 O(1)。新手拿到这题第一反应可能是新开一个数组倒着填或者用 JS 的 reverse 方法一步到位但后者显然违背了练习的初衷。双指针解法非常清晰左指针 i 从 0 开始右指针 j 从 s.length - 1 开始交换 s[i] 和 s[j]然后 i、j--直到 i j 停止。代码只有几行但这道题真正的价值在于提醒你注意循环条件到底是 i j 还是 i j。我个人建议用 i j因为在 i j 时交换的是同一个元素虽然不会报错但属于无意义的操作每次循环多浪费一次交换。这道题我用 JS 写过最朴素的版本/** * param {character[]} s * return {void} Do not return anything, modify s in-place instead. */ var reverseString function (s) { let left 0; let right s.length - 1; while (left right) { // 交换左右指针指向的字符 [s[left], s[right]] [s[right], s[left]]; left; right--; } };这里用了解构赋值来交换元素这是 JS 特有的写法非常简洁。如果你用的是其他语言就需要一个临时变量来做交换。另一个小坑是有些同学会把 right 初始化为 s.length然后循环条件写成 left right这样第一次操作会访问到 undefined输出结果莫名多出一个空元素。初始化的边界值一定要检查清楚我在这里吃过一次亏。3.2 经典题盛最多水的容器为什么移动值小的一边接下来是 LeetCode 第 11 题“盛最多水的容器”。题目大意是给一个非负整数数组每个数代表坐标点 (i, a[i]) 处的高度需要找到两条线与 x 轴围成的容器能装最多水。装水量等于两条线中较矮的那条高度乘以两条线之间的距离。最粗暴的思路是双重循环枚举每对组合时间复杂度 O(n²)数据量大时直接超时。双指针解法的思路是初始让左指针指向最左、右指针指向最右此时容器宽度最大。然后每次比较两条线的高度把较矮的那条对应的指针向中间移动一步同时更新最大面积。为什么这么做关键在于一个反证逻辑假设当前左右指针指向的高度分别是 h[left] 和 h[right]且 h[left] h[right]。此时面积 h[left] * (right - left)。如果尝试移动右指针也就是较高的那条边那么无论新右边的高度是多少新的宽度变小了而且容器的实际高度仍然受限于 h[left]。也就是说移动高指针的所有可能性都不会比当前面积更优。反过来如果移动较矮的左指针虽然宽度也变小了但新的高度有可能会变大从而有机会得到更大的面积。所以每一步移动矮边都是在排除一批“绝不可能超过当前最优解”的情况。这个“排除性”推理特别重要。我一开始学这题时写代码前没想通这个道理只是硬背“移动矮的”结果面到类似题稍微变形就卡住了。理解了推理过程之后你会发现这已经不是一个要背的规律而是一个可以随时复现的论证。具体的实现其实很短/** * param {number[]} height * return {number} */ var maxArea function (height) { let left 0; let right height.length - 1; let max 0; while (left right) { const width right - left; const h Math.min(height[left], height[right]); max Math.max(max, width * h); // 移动较矮的一侧 if (height[left] height[right]) { left; } else { right--; } } return max; };这段代码的时间复杂度是 O(n)空间复杂度是 O(1)。我实际测试时如果数据量在十万级别暴力法需要跑好几秒而双指针版本瞬间出结果。这道题还经常作为“双指针真的是最优解吗”的讨论题出现因为后置的“接雨水”问题表面上长得像但解法完全不同非常容易混淆这个区别我在后面常见问题里细说。3.3 进阶题三数之和的去重细节LeetCode 第 15 题“三数之和”是我个人认为双指针专题里坑最多的一道题也是面试高频题。题目要求找出数组里所有不重复的三元组使得三个数之和等于 0。暴力解法需要三重循环复杂度 O(n³) 完全不可接受。双指针的标准做法是先对数组排序固定一个数 nums[i]然后用左右指针在 i 后面的区间寻找两数之和等于 -nums[i]主要难点体现在去重上固定 i 后左指针从 i1 开始右指针从数组末尾开始。当前三数之和如果小于 0说明左指针的数太小左指针右移如果大于 0说明右指针的数太大右指针左移等于 0 则记录结果并同时收缩两个指针。去重是这道题真正的拦路虎。第一个去重点是固定的 i如果 nums[i] 和 nums[i-1] 相等直接跳过本次循环。第二个去重点是找到一组答案后左右指针的移动如果左指针右移后还是和刚才相同的值会生成重复的三元组必须继续跳过右指针同理。一个容易犯的错误是用 nums[i] 和 nums[i1] 比较跳过这会直接漏掉可能存在的有效组合比如数组里有两个相邻但不同的负数它们的组合可能是合法的。这个细节我在编码时栽过跟头建议你写完后多跑几个包含重复元素的用例验证。参考实现如下var threeSum function (nums) { nums.sort((a, b) a - b); const result []; for (let i 0; i nums.length - 2; i) { // 固定数去重 if (i 0 nums[i] nums[i - 1]) continue; let left i 1; let right nums.length - 1; while (left right) { const sum nums[i] nums[left] nums[right]; if (sum 0) { left; } else if (sum 0) { right--; } else { result.push([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--; } } } return result; };这道题还有一个进阶变形是找“最接近的三数之和”基本思路一致只是把相等判断改成更新最小差值去重逻辑可以简化甚至省略。如果你能独立写出三数之和再去写它大概只需要五分钟左右。4. 快慢指针实战拆解链表题几乎绕不开它4.1 环形链表 II从相遇推导入口LeetCode 第 142 题“环形链表 II”要求返回链表开始入环的第一个节点如果没有环则返回 null。这道题第一问通常简单——用快慢指针判断是否有环只要快指针能追上慢指针就说明存在环第二问“找入口”就需要多一层数学推导了。我先把结论摆出来快慢指针都从头节点出发慢指针每次走一步、快指针每次走两步它们在环内相遇后让其中一个指针回到头节点然后两个指针都以“每次走一步”的速度前进再次相遇的位置就是环入口。很多同学背这个结论但不知道原因。推导其实很关键我用自己的话说一遍。假设从链表头到环入口的距离是 a环入口到相遇点的距离是 b相遇点继续走到环入口的距离是 c。慢指针到相遇点时走过的距离为 a b。快指针到相遇点时走过的距离为 a b k(b c)其中 k 表示快指针在环里多绕了 k 圈k 至少为 1。由于快指针速度是慢指针的两倍所以a b k(b c) 2(a b)化简后得到a k(b c) - b (k - 1)(b c) c也就是说从链表头到环入口的距离 a等于从相遇点继续走 c 的距离再加上整数倍的环周长。让 ptr1 从链表头出发、ptr2 从相遇点出发都每次走一步ptr1 走到环入口花 a 步ptr2 同时走过 a 步等价于走过 c 再加若干整圈所以 ptr2 也正好停在环入口。这个推导过程值得亲手推一遍而不是只记结论。代码实现如下var detectCycle function (head) { if (!head || !head.next) return null; let slow head; let fast head; // 第一阶段快慢指针找相遇点 while (fast fast.next) { slow slow.next; fast fast.next.next; if (slow fast) { // 第二阶段从头和相遇点同步走 let ptr1 head; let ptr2 slow; while (ptr1 ! ptr2) { ptr1 ptr1.next; ptr2 ptr2.next; } return ptr1; } } return null; };需要注意一个边界问题while 循环里必须同时判断 fast 和 fast.next 是否存在因为快指针一次走两步如果 fast 本身为空或者 fast.next 为空fast.next.next 就会报错。这是一个非常经典的运行时错误来源。4.2 删除链表的倒数第 N 个节点一次遍历的写法LeetCode 第 19 题“删除链表的倒数第 N 个节点”常规做法是先遍历一遍得到链表长度 L再走 L - N 步找到待删节点的前驱。但如果面试官要求“一次遍历完成”快慢指针就派上用场了。思路是让快指针先走 N1 步然后快慢指针同步向前走当快指针走到链表末尾时慢指针正好位于待删除节点的前驱节点。为什么是 N1 而不是 N因为删除节点的关键是找到它的前一个节点快指针先走 N1 步慢指针与快指针之间刚好隔了 N 个节点这样当快指针到达 null 时慢指针恰好停留在倒数第 N1 个节点。这里还有一个很容易踩的坑如果链表长度恰好等于 N快指针先走 N1 步时可能会直接走到 null这时说明要删除的其实是头节点。需要单独处理直接返回 head.next。我的实现里用了一个“虚拟头节点”技巧避免对头节点做特殊判断推荐你也这样写var removeNthFromEnd function (head, n) { const dummy new ListNode(0); dummy.next head; let fast dummy; let slow dummy; // 快指针先走 n1 步 for (let i 0; i n; i) { fast fast.next; } // 快慢指针同步移动 while (fast) { fast fast.next; slow slow.next; } // 此时 slow 指向待删节点的前驱 slow.next slow.next.next; return dummy.next; };虚拟头节点的好处在于统一处理边界。类似这种“删除头节点”的场景如果不用 dummy代码就需要额外的分支判断更容易出错。这个技巧在链表类题目中适用性很强建议熟练掌握。4.3 竟然还能这样用快慢指针处理数组去重快慢指针不仅能处理链表在数组原地操作中同样是利器。LeetCode 第 26 题“删除有序数组中的重复项”就是典型例子。题目要求在原地删除重复出现的元素返回新数组的长度。常规做法可能是复制到一个新数组但这违反空间 O(1) 的限制。快慢指针的做法很巧妙慢指针 slow 指向最后保留的位置快指针 fast 用来遍历整个数组。当快指针发现新元素和慢指针指向的元素不同时就把新元素前移到 slow1 的位置然后 slow 右移。最终 slow1 就是新数组的长度。我最初写的版本有一个 bug把 fast 初始化为 0、slow 初始化为 0然后在 fast 指向的元素与 nums[slow] 相等时只移动 fast。这在大多数用例下是对的但遇到长度 1 的数组会出错因为循环根本不会进入最终返回的 slow 1 1 倒是恰好正确但如果我用 slow 当长度就错了。后来我统一采用“慢指针指向已处理区间的最后一个位置”的语义代码稳定很多var removeDuplicates function (nums) { if (nums.length 0) return 0; let slow 0; for (let fast 1; fast nums.length; fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; };这类“快针遍历、慢针维护结果”的思路还可以延伸到“移除元素”“移动零”等题目上。本质是同一个模板快指针负责扫描和筛选慢指针负责记录目标放置位置区别只在于具体条件不同。如果你把这几个题放在一起对比练习收获会翻倍。5. 复杂度分析为什么双指针能快这么多时间复杂度是面试必问的点也是很多人只会背结论、说不清原理的部分。简单来说左右指针和快慢指针在实际执行过程中两个指针各遍历一次数据整体是线性关系因此时间复杂度为 O(n)相比暴力枚举的 O(n²) 或 O(n³) 是质的飞跃。但有两个需要说透的地方。第一个是“为什么两个指针还是一层循环就比两层循环快”因为双指针通过数学或逻辑上的排除每一步都能确定性地淘汰掉一批不可能成为答案的候选而暴力枚举对所有候选组合逐一验证两者的操作规模完全不同。第二个地方是空间复杂度双指针只使用常数级别的额外变量所以空间复杂度为 O(1)这也是它适合在处理大规模数据时使用的关键优势。拿盛最多水的容器举个例子暴力法要比较 C(n, 2) 个组合而双指针法每一步都在排除一整列或一整行候选最终只需要 n-1 次比较。这就是“算法优化”最直观的体现。排序 双指针的组合复杂度也值得单独提一句。比如三数之和排序时间复杂度为 O(n log n)双指针扫描每层为 O(n)整体为 O(n log n) O(n²)。如果面试官追问能不能更快理论下界说明基于比较的排序至少是 O(n log n)所以这个复杂度在该模型下已经是合理答案。我面试某公司时面试官就指着三数之和的代码问“你排序花了 O(n log n)如果数组本身有序你的算法能优化到什么程度”答案是双指针部分维持 O(n²) 不变但由于省了排序整体从 O(n²) 降到了 O(n²)……实际上排序省不省对数量级没有影响。不过如果你能主动指出“数组有序时排序可跳过”这个优化点会显得思维更细致。6. 遗忘曲线友好型刷题法整理笔记的思路与工具说了这么多题目最后聊聊我是怎么做笔记体系的。很多朋友刷题踩的坑不是刷得不够多而是刷完从来不回头看遗忘速度快得惊人。我个人常用的方法是“主题式总结 间隔回顾”按专题整理每类题型的套路、代码模板、易错点然后在第 1 天、第 3 天、第 7 天各回顾一次对应模板。具体到双指针专题我的笔记结构是四段第一段写“什么信号能想到双指针”第二段贴最小可运行模板左右指针一个、快慢指针一个第三段列这个专题里我踩过的全部坑比如下标边界、循环条件、去重时机第四段放题目索引每道题标注难度、关联标签和一句话思路。这样刷到新题时先翻第四段找相似题对比再翻第三段提醒自己不要重复踩坑。工具上我保持极简原则普通文档就够了。题解和注释我都写在 LeetCode 官方编辑器的代码注释里这样重刷题目时能直接看到当时的思考过程。分类索引单独维护在文档中按专题拼接方便横向查看。另外我用了一个笨办法每个专题设置一个“挑战问题”比如双指针专题就是“能不能不看题解用 10 分钟把三数之和完整写出来”。如果挑战失败就再回到笔记里看一遍易错点然后隔天再挑战一次。这个方法不一定适合所有人但对我这种记性一般、又不想反复刷同题的人来说效果明显。如果你也总感觉“做了很多题但脑子里没留下什么”可以试试。7. 常见坑位速查表与面试表达技巧为了防止以后翻笔记时又踩相同的坑我把双指针专题遇到的典型问题整理成了一张速查表典型问题根因避坑建议快指针越界访问一次走两步前没判断 fast.next 是否存在while (fast fast.next) 双重判断循环条件用了 i j 导致多余操作指针相遇时元素无需处理统一用 i j 收尾三数之和去重逻辑漏掉重复组合只在循环体外层去重忘了内层去重找到一个解后左右指针同时跳过重复元素删除倒数第 N 个节点时忘记链表长度等于 N 的场景快指针走到 null慢指针位置不对使用虚拟头节点 dummy原地去重时返回值与数组长度混淆slow 的语义模糊明确语义为“最后一个保留元素的下标”长度是 slow1反转字符串把 right 初始化为 len边界多 1首次访问越界初始化为 len - 1面试中讲双指针题时还有一个我学到的表达技巧不要一上来就报答案而是先描述暴力解法再点出“复杂度不可接受”然后说“能不能用双指针减少一层循环”接着用一句话说明“每次移动指针时为什么可以排除一部分情况”最后给出复杂度。这样的叙述节奏面试官基本不需要追问就能理解你的思路也会觉得你真有算法思维而不是背题。我个人体会讲清楚“为什么移动这个指针而不移动另一个”是双指针题拿高分的分水岭。很多人能把代码写对却说不清理由这样一旦题目变形就容易露怯。如果你只能记住一句话把这句话留给“排除不可能最优解”的推理一定不亏。