优化实战)
★ FEATURED ARTICLE 1. 双指针为何是蓝桥杯高频考点四种模式与出题套路准备蓝桥杯的同学应该都有同感有些题一看到“数组”“有序”“连续子串”这些字眼脑子里就该立刻弹出双指针这个选项。它不是某一种固定的算法而是一组“用指针维护区间状态”的思维模式。很多 O(n²) 的暴力解法换成双指针之后能压到 O(n)而且空间基本是 O(1)这在竞赛里属于性价比极高的优化手段。双指针最常见的用法可以分成四种对撞指针两个指针一左一右向中间移动典型场景是有序数组里找两数之和、反转数组、回文判断。快慢指针两个指针同向移动但速度不同典型场景是链表判环、找链表中间节点、删除倒数第 K 个节点。滑动窗口本质上是同向双指针left 和 right 维护一个窗口right 负责扩张left 负责收缩典型场景是子串、子数组问题。归并型指针两个指针分别指向两个有序序列按大小顺序依次合并典型场景是合并两个有序数组、合并两个有序链表。蓝桥杯历年真题里双指针很少作为单独的“压轴题”出现但它经常作为一道中等难度题的核心解法或者作为优化步骤嵌在搜索、动态规划、数据结构题里。比如“三数之和”“接雨水”“最长回文子串”这类题目如果你只掌握暴力思路数据范围一大就超时但如果提前练熟了双指针就能很快意识到可以用左右指针把枚举维度降一维。所以与其零散地刷题不如把四种模式一次性吃透。下面我用四道经典例题把对撞、快慢、滑动窗口、归并这四种双指针逐一拆开讲每道题都会说清楚暴力思路为什么不行、双指针为什么对、代码怎么写、哪些地方最容易踩坑。这几道题都是蓝桥杯模拟赛和往届省赛里反复出现过的原型题变形很多值得好好消化。2. 例题一有序数组两数之和对撞指针2.1 题目描述与暴力思路题目原型是给定一个按升序排列的整数数组 nums 和一个目标值 target请在数组中找出两个数使它们的和等于 target返回这两个数的下标从 1 开始计数。保证有且仅有一组答案。第一反应当然是两层循环枚举外层固定第一个数内层找第二个数。时间复杂度 O(n²)空间 O(1)。如果数组长度是 10⁵那就是 10¹⁰ 次操作蓝桥杯评测机基本跑不动。而且题目只要求一组解硬枚举显然浪费了数组“升序”这个关键条件。2.2 对撞指针的移动规则与正确性证明升序数组最大的好处是大小关系是确定的。我们可以让 left 指向最左边right 指向最右边然后看当前两个数的和如果 nums[left] nums[right] target直接返回答案。如果和小于 target说明整体太小了需要让和变大。left 向右移动因为 nums[left] 是当前区间内最小的数之一left 右移会让当前左侧数变大从而整体和变大。如果和大于 target说明整体太大了需要让和变小。right 向左移动因为 nums[right] 是当前区间内最大的数right 左移会让整体和变小。为什么这样不会漏掉答案因为每一步都在排除不可能的区间。假设正确答案是 (i, j)如果当前 left 在 i 的左边那么 left right 的和一定小于 target因为 left 位置的值小于等于 nums[i]而 right 位置的值不会超过 nums[j]所以 left 会一直右移到 i反之如果 right 在 j 的右边那么 left right 的和一定大于 targetright 会一直左移到 j。整个过程最多移动 n 次时间复杂度 O(n)。2.3 C 代码实现与易错点vectorint twoSum(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { return {left 1, right 1}; // 题目要求从1开始 } else if (sum target) { left; } else { right--; } } return {}; }这里有几个特别容易翻车的地方循环条件到底写left right还是left right这道题要求两个不同的数所以必须写left right。如果写left right当 left 和 right 指向同一个元素时会错误地把它自己当成两个数。返回下标时一定要注意题目要求的是从 0 开始还是从 1 开始。蓝桥杯经常把输入输出改成从 1 计数返回的时候别漏了1。如果数组里存在重复元素对撞指针依然有效因为只要有一组答案指针一定会收敛到某一组答案上不需要额外去重。但如果题目要求输出所有不重复的二元组就需要在找到一组答案后跳过重复元素。2.4 举一反三三数之和与最接近的三数之和这道题最经典的变形是“三数之和”给定数组找出所有和为 0 的三元组。做法是先排序然后固定第一个数剩下两个数用对撞指针来找。排序 O(n log n)固定第一个数 O(n)对撞指针 O(n)总复杂度 O(n²)比三重循环的 O(n³) 好一个量级。另一个变形是“最接近的三数之和”思路类似只是不需要严格相等而是在移动指针的过程中不断更新最小差值。这类题在蓝桥杯省赛里出现过类似思路所以建议把“两数之和”的对撞模板背到条件反射的程度。3. 例题二最长无重复字符子串滑动窗口3.1 题目描述与分析切入点题目原型是给定一个字符串 s找出其中不含有重复字符的最长子串的长度。比如 s abcabcbb结果是 3因为最长无重复子串是 abc。暴力做法是枚举所有子串检查每个子串是否有重复字符复杂度 O(n³) 甚至 O(n²)。显然不行。再仔细观察这个问题其实可以用“窗口”来理解窗口内永远保持无重复字符右指针向右扩张一旦发现当前字符已经在窗口里出现过就移动左指针收缩窗口直到窗口重新合法。3.2 滑动窗口的实现细节用数组记录最后出现位置这里我用一个长度为 128 的数组 last 来记录每个字符最近一次出现的位置下标从 1 开始记用 0 表示尚未出现。left 表示当前窗口的左边界right 表示当前正在考察的字符下标。核心逻辑是当 right 位置的字符在窗口内出现过last 记录的位置不小于 left就把 left 移动到 last 记录的位置加 1从而跳过重复字符。然后更新 last 记录同时计算窗口长度 right - left 1更新答案。这里有一个关键点很多人第一次写会直接left last[s[right]] 1但这样不严谨因为 last 记录的上一次出现位置可能已经在当前 left 的左边了。比如字符串 abba遍历到最后一个 a 时last[a] 是 0但当前窗口 left 已经是 2 了如果直接取 last 加 1left 会倒退导致窗口出现重复字符。所以必须写成left max(left, last[s[right]] 1)。3.3 代码与复杂度int lengthOfLongestSubstring(string s) { vectorint last(128, 0); int left 0, ans 0; for (int right 0; right s.size(); right) { char c s[right]; left max(left, last[c]); // last[c]存的是上次出现位置1注意约定 ans max(ans, right - left 1); last[c] right 1; // 记录为下次遇到该字符时left至少跳到这个位置 } return ans; }注意这里我约定last[c]存储的是“如果当前字符重复left 应该跳到的位置”也就是上次出现下标加 1。这样初始化全 0 时left 取 max 不会出错。时间复杂度 O(n)空间 O(128)可以认为是 O(1)。为什么 left 不需要回退因为窗口只向右扩张left 也只会向右移动这是滑动窗口能保持 O(n) 复杂度的重要原因。如果你用 set 来维护窗口每次重复时需要从 set 里删除 left 对应的字符虽然也能做但删除和查找的常数更大而且代码更绕不如数组记录位置直观。3.4 常见误解与真题变形这道题在蓝桥杯里的变形很多最常见的两个含有 K 种不同字符的最长子串窗口合法条件从“无重复字符”变成“不同字符数不超过 K”仍然用滑动窗口只是需要额外维护窗口内字符种类数。字符串排列判断 s2 是否包含 s1 的某个排列同样可以用固定长度的滑动窗口配合字符计数数组来判断。我见过不少同学在这道题上写错主要是因为 left 的更新没有取 max导致窗口范围错误。建议在练习时多打印几组 left、right 和当前窗口内容比如 tmmzuxt 这种用例手动走一遍就能理解 max 的重要性。4. 例题三环形链表快慢指针4.1 链表判环的经典思路题目原型是给定一个链表判断链表中是否有环。如果链表中有某个节点可以通过连续 next 指针再次到达则说明有环。直观想法是用哈希表记录访问过的节点如果遇到重复节点就是有环。时间复杂度 O(n)空间 O(n)。但链表题更喜欢 O(1) 空间的解法于是就有了快慢指针。设 slow 每次走一步fast 每次走两步。如果链表没有环fast 会先到达末尾 null过程结束。如果有环slow 和 fast 最终一定会在环内相遇。为什么可以想象两个人在环形跑道上跑步slow 速度是 1fast 速度是 2相对速度是 1相当于 fast 每走一步就离 slow 更近一步所以必定追上。4.2 代码实现循环条件与空指针保护bool hasCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }这里的循环条件必须同时判断fast ! nullptr和fast-next ! nullptr因为 fast 一次跳两步如果不判断fast-next访问fast-next-next会崩溃。slow 不需要额外判空因为 fast 都走完了slow 一定还在。4.3 进阶如何找到环的入口判断是否有环只是第一步蓝桥杯偶尔会考“返回环的入口节点”。数学推导是这样的设链表头到环入口距离为 a环入口到相遇点距离为 b相遇点继续走到环入口距离为 c环长为 L b c。slow 走了 a bfast 走了 a b kLk 圈由于 fast 速度是 slow 的 2 倍所以 2(ab) abkL得到 a kL - b (k-1)L c。也就是说从相遇点出发和从链表头出发每次各走一步它们会在环入口相遇。所以实现就是先找到相遇点然后把一个指针移到链表头两个指针同时每次走一步相遇点就是环入口。代码在 hasCycle 的基础上扩展即可。4.4 快慢指针的其他应用找中点与倒数第 K 个节点快慢指针不只是用来判环。找链表中间节点slow 走一步fast 走两步fast 到达末尾时 slow 恰好在中点。这在归并排序链表、回文链表判定里很常用。找倒数第 K 个节点让一个指针先走 K 步然后两个指针同步走先走的指针到达末尾时后走的指针指向的就是倒数第 K 个节点。这类“同向不同速”的用法在蓝桥杯链表题里出现频率很高建议一并练习。5. 例题四合并两个有序数组归并型指针5.1 题目描述与常规误区题目原型是两个升序整数数组 nums1 和 nums2nums1 的长度为 mn前 m 个元素是有效元素后 n 个位置空闲填充 0nums2 的长度为 n。要求将 nums2 合并到 nums1 中使 nums1 仍然有序且不返回新数组原地修改。很多同学拿到题先想到的是新建一个临时数组双指针归并然后再拷贝回 nums1。这样空间复杂度 O(mn)能过但不优雅。题目既然在 nums1 后面预留了空闲位置就是希望我们从后往前合并避免覆盖有效元素。5.2 从后往前的归并策略详解设置三个指针p1 指向 nums1 有效部分的末尾即 m-1。p2 指向 nums2 的末尾即 n-1。p 指向合并后数组的末尾即 mn-1。每次比较 nums1[p1] 和 nums2[p2]把较大的元素放到 nums[p]然后对应的指针前移。如果 p1 或 p2 先小于 0就把另一个数组剩余的元素依次填入。为什么从后往前是对的因为 nums1 后面的位置是空的从后往前填不会覆盖 nums1 前半段的有效数据。如果从前往后填每插入一个 nums2 元素nums1 的有效元素就可能会被覆盖必须移动其他元素复杂度就上去了。5.3 代码实现void merge(vectorint nums1, int m, vectorint nums2, int n) { int p1 m - 1, p2 n - 1, p m n - 1; while (p1 0 p2 0) { if (nums1[p1] nums2[p2]) { nums1[p--] nums1[p1--]; } else { nums1[p--] nums2[p2--]; } } while (p2 0) { nums1[p--] nums2[p2--]; } }注意最后只需要处理 p2 剩余的情况因为如果 p1 还有剩余它们已经在 nums1 的合适位置上了不需要移动。5.4 归并思想的延伸合并两个有序链表同一个归并思路也能用到链表上新建一个哨兵节点两个指针分别指向两个链表的头节点每次把值较小的节点接到结果链表的尾部直到其中一个链表为空再把另一个链表剩余部分接上去。时间复杂度 O(mn)空间 O(1)。这道题虽然简单但它体现了双指针的一种重要用法不是维护窗口而是维护两个独立序列的遍历进度。很多复杂题目比如“寻找两个正序数组的中位数”“有序矩阵中第 K 小的数”底层都用到了类似的归并或者双指针逼近思想基础必须打牢。6. 双指针高频踩坑点现场调试心得与避坑指南6.1 最容易犯的五个错误双指针代码写起来短但错误率并不低。我把这几年带选手训练时遇到的典型问题整理成了表格几乎每一届都有同学踩中同样的坑。问题场景错误写法正确做法对撞指针条件while (left right)如果要求两个不同元素用left right滑动窗口 left 更新left last[c] 1left max(left, last[c] 1)防止 left 回退快慢指针快节点移动while (fast-next)while (fast fast-next)否则可能空指针崩溃从后往前归并后处理需要处理两个剩余数组只需处理第二个数组剩余第一个数组天然在正确位置答案更新时机在 left 移动前更新要保证当前窗口合法后再更新 ans顺序很重要6.2 比赛现场的调试技巧双指针的调试我一般建议三步走。第一步小规模用例手推。比如对撞指针用[1,2,3,4,5], target7手动走一遍 left 和 right 的变化滑动窗口用abcabcbb走一遍窗口收缩过程。手推能发现逻辑层面的大问题。第二步在代码里临时输出中间变量。很多 OJ 不允许打印但本地编辑器可以。打印 left、right、当前窗口内容、指针指向的值一眼就能看出问题是移动方向反了、条件写反了还是更新顺序错了。记得调试完删掉打印语句。第三步检查边界条件。数组为空、只有一个元素、全部元素都相同、左右指针相邻、目标值极大极小这些用例都要过一遍。很多边界问题在蓝桥杯的评测数据里是专门用来构造的代码写得再漂亮边界考虑不周全照样扣分。6.3 如何判断一道题能不能用双指针这是最核心的竞赛能力。我总结出三个信号第一数据范围暗示 O(n) 解法。如果 n 在 10⁵ 到 10⁶ 左右O(n log n) 还可以接受O(n²) 大概率超时双指针往往是优先考虑的方向。第二问题涉及“连续区间”或“有序序列”。比如子串、子数组、区间和、链表环、有序数组找数这些结构天然适合用指针维护区间。第三暴力解法中存在大量冗余枚举。比如两数之和里对每个 left 都重新扫描一遍 right滑动窗口里对每个起点都重开一个窗口扫描。如果我们能利用单调性消除冗余双指针就是那把钥匙。蓝桥杯想拿省一双指针不是万能的但没有双指针是万万不行的。我个人的经验是与其考前刷一百道“模板题”不如把这四种模式对应的经典例题和变形整理成一套自己的解题笔记。比赛时看到一个题先在脑子里过一遍“这题是对撞、快慢、滑动窗口还是归并”然后直接套已经验证过的模板再针对题目细节调整边界条件。这个过程熟练之后基本可以把双指针题的通过时间压缩到十分钟以内。最后再分享一个小技巧练习时不要把四道题分开看可以尝试把它们的核心代码都默写一遍。默写不是为了背题而是为了让手和脑形成肌肉记忆。等到上了赛场哪怕遇到双指针的变形题你也会发现自己更容易读懂题面背后的指针运动规律。
阅读完成 · 觉得有帮助？
