★ FEATURED ARTICLE 很多同学在备赛蓝桥杯的时候一提到“双指针”三个字第一反应是这不就是两个下标来回挪吗确实双指针表面上看没什么高深理论但真到了考场里边界条件一出错多写一个i少写一个j--整道题就全乱了。更麻烦的是双指针不是一个固定算法而是一类“用两个变量去扫描序列”的思考方式不同的题目套路完全不同。这篇文章我把蓝桥杯里出现频率最高的四类双指针题一次性拆开讲透排序数组里的两数之和、无重复字符的最长子串、原地去重与删除元素、盛最多水的容器。这四个题基本覆盖了双指针的所有常见套路相向夹逼、滑动窗口、快慢同步、左右贪心。搞懂这四个题你上考场拿到新的双指针题至少能一眼识别出该往哪个方向走。文章不会绕弯子直接按“怎么想、为什么能这么做、代码怎么写、有哪些坑”的顺序讲代码用 C 写但核心思路换成 Java、Python 完全一样。1. 双指针算法的核心思路与适用场景1.1 双指针的本质把两重循环变成单重循环双指针的本质是用两个变量在序列上做有方向的移动让原本需要两层循环枚举所有组合的问题变成一层循环加若干次指针移动。听起来像玄学我拿生活场景打个比方。假设体育老师带着全班同学做“两人三足”分组测试如果要求把所有两两组合都试一遍那是 O(n²) 的工作量。但老师换个办法让一队从前往后走一队从后往前走两个人碰头时根据当前情况决定谁继续走整个过程只需要走一圈。双指针干的就是这件事。所以它解决的问题有一个共同特征序列本身带有某种有序性、单调性或者题目存在可以排除的搜索空间。一旦某个指针移动后原来方案里的某一部分解就再也不会被需要了。这也是为什么双指针的代码通常很短但“为什么移动这个指针”这个问号比代码本身更重要。我见过很多同学把代码背下来了结果题目稍微改一个条件比如从“严格递增”变成“非严格递增”代码就废了本质就是没理解指针移动的数学依据。1.2 双指针的三大常见套路双指针按照“移动方式”大致能分成三类我先把模板立起来后面四个例题依次往里套。第一类是相向双指针也叫左右指针。一个指针放在数组开头一个放在数组末尾每次根据当前判断决定移动左边还是右边。典型场景是排序数组中的两数之和、翻转数组、回文判断。这类问题的前提通常是数组有序或者存在某种单调性使得我们可以放心地“舍弃”某一侧。第二类是快慢双指针两个指针同方向出发速度我可以通过手动控制来模拟“快慢差”。典型场景是链表找环、原地去重、移除指定元素。快指针负责向前探路慢指针维护结果数组的末端相当于把“空间覆盖”这个过程稳定下来。第三类是滑动窗口左右指针都从左端出发右指针不断右移扩张窗口当窗口内条件不满足时左指针右移收缩窗口。典型场景是子串问题、子数组问题无重复字符的最长子串、长度最小的子数组。滑动窗口本质上是快慢指针的一种升级版区别在于右指针每走一步窗口内状态都要被维护和检查。很多同学会问这三个套路看着不一样怎么判断一道题用哪个我自己的判断标准很简单如果两个指针的移动方向相反大概率是相向双指针如果方向相同且一个快一个慢大概率是快慢指针如果把“子数组/子串连续性”作为约束条件优先想滑动窗口。1.3 为什么蓝桥杯爱考双指针蓝桥杯这类算法竞赛和纯算法岗面试有一个很大的不同它非常看重“在有限时间内把思路转化成可运行代码”的能力。双指针代码短、运行快、逻辑直观但恰恰能在小细节里拉开差距所以命题人很爱把它塞到中等难度题里当“核心考点”。从比赛数据看双指针常常以两种形式出现。第一种是作为题目的主算法比如“在一个有序数组中找到两个数使它们的和等于 target”你要是不会双指针就只能 O(n²) 暴力在n10^5的规模下直接超时。第二种是作为优化前置步骤比如某些二维 DP 或前缀和题先排序再用双指针把一维部分从 O(n²) 优化到 O(n)这一步直接决定能否在时限内通过。另外双指针也承担了“考察边界处理能力”的任务。蓝桥杯的评测数据往往很“毒”会塞空数组、只有一个元素的数组、全部相同的数组、溢出临界值等情况而这些恰好是双指针最容易翻车的地方。吃透这类题不只是在学一个技巧更是在锻炼对输入数据敏感性的判断这是比赛中最有价值的能力之一。2. 四大经典例题逐题拆解2.1 例题一排序数组中的两数之和相向双指针题目描述给定一个按非递减顺序排序的整数数组和一个目标值 target要求找出两个数使它们的和等于 target返回这两个数在数组中的下标下标从 1 开始。第一眼看到“有序数组找两个数”最常见的思路是双重循环枚举所有数对。这个思路没毛病但在数据量大一些的蓝桥杯题目里O(n²) 会直接超时所以必须换一个更快的方法。双指针思路非常直白。我把左指针放在数组最左边右指针放在数组最右边每次计算nums[left] nums[right]。如果这个和恰好等于 target直接返回答案如果小于 target说明当前和太小了为了让和变大一点只能让左指针往右移因为右指针已经是最右边的数了往左移只会让和更小如果大于 target说明当前和太大了我们需要让和变小一点这时候只能把右指针往左移。这个逻辑的背后是“单调性”。因为数组有序所以右指针固定时左指针越右移和越大左指针固定时右指针越左移和越小。我们每次移动指针都排除掉了一整列或一整行的候选解效率自然高。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}; } else if (sum target) { left; } else { right--; } } return {-1, -1}; }代码中left right作为循环条件很关键。如果写成while (left ! right)在极端情况下可能会出现left right之后还在死循环或者越界访问。另外要注意题目给的是“下标从 1 开始”所以返回left 1, right 1。这是蓝桥杯特别喜欢设置的细节陷阱读题不仔细直接丢分。我见过一个很经典的变式把“和等于 target”改成“和小于 target 的数对有多少个”。这时候不需要返回下标而是用计数器统计每找到一个满足条件的区间就累计right - left个答案。本质上还是同一个框架但多了个统计维度。遇到这种变式时你得想清楚当nums[left] nums[right] target时left 固定left 到 right 之间的所有数都能和 left 组成合法数对所以一次就能累加多个解。2.2 例题二无重复字符的最长子串滑动窗口题目描述给定一个字符串请你找出其中不含有重复字符的最长子串的长度。这道题是滑动窗口的经典代表在蓝桥杯的字符串题里也经常出现而且往往不是直接让你求长度而是让你在求长度的过程中同时维护子串的起始位置为后续输出做准备。暴力做法是枚举所有子串再逐一检查是否有重复字符这种 O(n³) 的思路在大数据下完全不可行。滑动窗口的做法则把问题拆成两件事右指针负责扩展左指针负责收缩。具体步骤是右指针不断向右走每走到一个新字符就把它在字符计数数组里的次数加一。如果某个字符出现的次数大于 1说明当前窗口里面有重复了于是左指针开始向右收缩把左指针指向的字符次数减一然后左指针右移直到窗口重新满足“无重复字符”的条件。每次右指针走完一步且窗口合法后记录一下当前窗口长度取最大值。int lengthOfLongestSubstring(string s) { int cnt[128] {0}; int left 0, right 0, ans 0; int n s.size(); while (right n) { cnt[s[right]]; while (cnt[s[right]] 1) { cnt[s[left]]--; left; } ans max(ans, right - left 1); right; } return ans; }我特别强调一下cnt[s[right]]这个判断条件看起来是看“当前字符有没有重复”实际上它已经把窗口内所有字符的状态都维护好了。如果当前窗口有别的字符重复不会立刻影响这里因为cnt[s[right]]不超过 1窗口会被认为合法但实际上是错的。所以请记住这个 while 循环的条件通常是“cnt[s[right]] 1”因为新进入的字符是唯一可能导致当前窗口不合法的角色。有个细节很多新手会踩坑字符可能不只是 ASCII 码如果字符串里包含中文或特殊扩展字符cnt[128]就不够用了。比赛里如果声明字符串只含小写字母用 26 就够如果没说建议直接开cnt[256]甚至用哈希表。别在这种地方省空间一旦越界就是运行时错误整道题直接白给。滑动窗口的复杂度是 O(n)因为左右指针各自最多移动 n 次。这个复杂度也是蓝桥杯里出题人希望你达到的量级。如果题目允许字符集很小比如只有小写字母其实还可以用位运算来记录窗口内字符是否出现那是进阶玩法先把基础的 count 数组练熟再说。2.3 例题三原地去重快慢双指针题目描述给定一个非严格递增排序的数组你需要在原地删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。要求不能使用额外的数组空间必须原地修改输入数组。“原地”两个字一出来基本就是把额外空间卡死新手最常见的错误就是开一个新的 vector 或数组来存结果。正确解法用双指针慢指针负责记录“当前已经整理好的唯一元素区间的末尾”快指针负责向前扫描整个数组。初始时慢指针在 0 的位置快指针从 1 开始。每次快指针遇到一个和慢指针指向元素不同的值就先将慢指针右移一位再把快指针指向的值赋值给慢指针位置。如果快指针遇到的值和慢指针相同说明这个值已经出现过直接跳过。int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int slow 0; for (int fast 1; fast nums.size(); fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; }问自己一个问题为什么slow从 0 开始而fast从 1 开始因为第一个元素一定保留。数组即使全是重复元素至少也有一个元素不需要删。如果上来就把slow设为 -1处理起来反而更绕。还有个关键操作是“赋值覆盖”。有些同学会担心直接覆盖会不会把后面还没遍历到的元素弄丢放心因为快指针一直在慢指针前面慢指针指向的位置要么是原来的旧值要么是已经被快指针扫描过的位置不会影响后续操作。这个题在蓝桥杯里最常见的变体是“移除指定值的元素”要求移除所有值等于 val 的元素返回新长度。思路几乎一模一样只是判断条件从“是否不同”变成“是否不等于 val”。int removeElement(vectorint nums, int val) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; slow; } } return slow; }注意这个题和去重有一个重要区别初始时slow和fast都从 0 开始因为第一个元素也可能等于 val需要被移除。每次赋值后才移动 slow最终返回 slow 而不是 slow 1因为它直接代表了“剩余元素个数”。两个题模板就差一行但错的后果完全不同做题时一定要先搞清楚“第一个元素是否一定保留”。2.4 例题四盛最多水的容器左右贪心题目描述给定 n 个非负整数每个数代表坐标 (i, a[i]) 处的一条竖线。找到其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。这道题看名字好像和生活有关实际上是一个典型的“左右夹逼”问题。很多人第一反应是暴力枚举所有两根柱子的组合但 O(n²) 在数据量大时必挂。双指针解法同样把左指针放在最左右指针放在最右。容器能装多少水取决于较短的那条柱子也就是min(height[left], height[right])宽度是right - left。每次算出当前容器的面积记录下来然后移动较短的柱子那一侧。为什么移动较短的一侧因为当前容器的瓶颈是较短的那根柱子。如果我们移动较长的一侧新的柱子即使再长容器高度依然被较短的那侧限制而且宽度还变小了面积不可能更大。只有移动较短的一侧才有机会让“短板变长”从而在宽度减小的情况下提高面积。int maxArea(vectorint height) { int left 0, right height.size() - 1; int ans 0; while (left right) { int area (right - left) * min(height[left], height[right]); ans max(ans, area); if (height[left] height[right]) { left; } else { right--; } } return ans; }这道题有一段“反直觉”的推理很多人第一次看会半信半疑移动较短的一侧会不会错失最优解不会。因为当前状态下较短的一侧已经决定了任何包含该位置且另一端在当前区间内的容器都不可能超过当前宽度和该高度构成的上限。也就是说每一轮移动都排除掉了一根柱子作为边界的所有可能性而且这些可能性不会包含全局最优解。每一轮排除一种情况最后收敛到答案。这个题的变体是“接雨水”即给定柱子高度计算能接多少雨水。接雨水比盛水容器更复杂因为它要考虑每个位置上方存水的量和柱高整体分布有关。但如果用双指针做核心思想同样是维护左右两个指针和两侧的最高高度逐列累加雨水。通常建议先把盛水容器彻底吃透再去看接雨水这样理解曲线更平滑。蓝桥杯里还有一个常见考法是“最大矩形面积”给定一排柱子高度找最大矩形面积。乍一看和盛水容器像但实际上需要用单调栈而不是双指针。碰到这种题要时刻提醒自己双指针不是万能药只有具备单调性或者能安全排除搜索空间时它才是最优解。3. 常见问题与排查技巧实录3.1 边界条件反复出错问题出在哪我在帮人复盘代码的时候发现双指针题出错的位置高度集中几乎都集中在三件事上循环条件、指针初始值、指针移动时机。以两数之和为例循环条件写while (left right)、while (left right)、while (left ! right)三个写法在某些数据下都能正常跑但面对“数组长度为 1”“找不到答案”的情况表现完全不同。最稳妥的做法是统一用left right因为它天然限制了 left 和 right 不能指向同一个元素也能防止越界。尽量别用left ! right因为这种写法在某种情况下可能让 left 直接越过 right下一轮访问nums[left]就越界了。指针初始值更要警惕。比如原地去重第一个元素是否一定保留移除元素第一个元素是否一定保留这两个问题的答案不一致导致初始值不能生搬硬套。我见过有人背了去重的模板结果到移除元素题里也把 slow 设成 0 然后从 fast1 开始最后把第一个等于 val 的元素漏掉了。做题前先想清楚“第 0 个位置需不需要被检查”而不是先背模板。指针移动时机是最后一个高频坑。比如滑动窗口里到底是先移动 left 再更新答案还是先更新答案再移动 left这取决于窗口合法的判断时机。在“无重复字符最长子串”里我们保证窗口内无重复后再更新答案所以先执行 while 循环收缩再计算长度。要是顺序反了窗口可能仍处于非法状态答案就会偏大。3.2 死循环与越界两个最让人头大的运行时错误死循环和越界是双指针代码最容易出现且最难定位的运行时错误。你看着代码逻辑半天也想不明白其实问题往往出在“指针没有按照预期前进”。死循环最常见的场景是内层 while 循环的收缩条件一直为真导致 left 不断右移最终越过 right但外层循环条件又没及时退出。比如滑动窗口里如果cnt数组是局部变量并且没有正确清零或者某个字符计数没有随 left 移动而减一那么cnt[s[right]] 1可能会一直为真left 一路越界。越界访问的另一个隐藏原因是“空数组”。不管哪类双指针第一行最好都写个空判断。尤其像盛水容器和两数之和如果输入数组长度为 0直接访问nums[right]就是未定义行为。蓝桥杯的评测不会因为“数据太简单就不测空数组”这些边界数据恰恰是拉开分数的点。我自己的调试习惯是先人工模拟一遍小数据比如nums {2, 3, 4}把每一步的 left、right 值写在纸上再对着代码看每一步是否一致。这个过程看着笨但比在代码里到处打 print 更有效因为双指针的“状态转移”本来就适合在纸上推演。3.3 竞赛环境中的编码习惯与自查方法蓝桥杯的评测环境通常对代码长度、变量命名没有强制性要求但你自己的代码可读性一定要保证。比赛时精神高度紧张如果变量名都是a、b、l、r混用调试起来会非常痛苦。我建议至少把left、right、slow、fast这类带语义的名字写完整哪怕代码多打几个字母换取的是调试时的清晰度。还有一点尽量把答案更新放在一个统一的位置不要在 if 分支里散落多处更新。统一的位置能降低“漏更新”或“误更新”的概率。提交之前有一个我屡试不爽的自查清单先想一遍空数组、单元素数组、全相同数组、完全有序数组这四种输入然后想一想如果 target 特别大或特别小会不会有整数溢出最后再想一遍循环退出后 left 和 right 的最终位置判断它们是不是可能构成下一个非法访问。这四步走完绝大多数低级错误都能被挡在提交之前。我把常见的边界错误整理成了一张速查表方便你比赛前快速扫一眼问题类型常见错误正确做法两数之和返回下标忘了加 1看清题目要求的下标起始位置两数之和循环条件死循环统一使用left right滑动窗口窗口非法时仍更新答案先收缩到合法再更新滑动窗口字符计数数组太小按题目字符集大小申请空间原地去重第一个元素保留判断错误去重题 slow 从 0 开始移除元素把去重模板硬套移除题 slow 从 0 开始且可选 val盛水容器移动了较高的柱子每轮移动较矮一侧所有双指针空数组直接访问下标先判空再取元素4. 从读懂到熟练双指针的练习路径4.1 怎么判断一道新题能不能用双指针很多同学刷题越多越迷茫原因是“为了用双指针而用双指针”没有形成判断逻辑。我总结了一个三步判断法每步都是一个问题。第一步问题是否涉及“子序列/区间/两个元素组合”如果是说明大概率可以用双指针扫描。第二步序列上是否存在某种单调性或者有序性哪怕不是整体有序只要左右移动时能产生单调的“合法/非法”变化双指针就有戏。第三步暴力枚举的 O(n²) 是否无法承受如果数据规模很小暴力也能过那你想用双指针只是为了练习但比赛里没必要冒险。数据规模在10^5以上且问题适合双指针就该是你的首选。这套判断法在蓝桥杯真题里特别实用。你拿到题目后先看数据范围再看问题问的是子段、子串还是数对最后问自己“left 移动和 right 移动是否会改变解的搜索范围”。三个问题都能得到肯定回答就放心写双指针。4.2 从读题到 AC 的标准步骤我整理了一条建议路径特别适合备赛阶段。第一步把题意翻译成可操作的数据结构。比如“子串”对应字符串“子数组”对应数组“数对”对应两个下标。第二步画出指针移动示意图。我习惯先假设一组简单数据手动走一遍流程确定 left 和 right 的初始位置、结束条件、每次移动的触发条件。第三步确认每一轮移动都会缩小搜索空间且缩小后不会丢掉最优解。这是双指针正确性的根本。第四步写代码。第五步按 3.3 里的自查清单检查边界。这个流程看着慢但练习阶段慢就是快。我见过太多人直接对着题解敲代码敲完觉得自己会了结果十天后遇到同类型题还是一脸懵。原因就是跳过了第二、第三步只记住了答案的函数名没记住思考路径。4.3 进一步扩展四题之外的变体方向把四道例题吃透之后可以尝试几个方向来巩固。第一个方向是“三数之和”。排序后固定一个数剩下两个数用双指针去扫整体复杂度从 O(n²) 降到 O(n²)虽然还是平方级但比暴力 O(n³) 好得多。第二个方向是“长度最小的子数组”目标是找出和大于等于 target 的最短连续子数组这是滑动窗口的变体收缩条件变成了“窗口内的和足够大时尝试左移”。第三个方向是“链表的中间节点”或“链表环检测”这两个是快慢指针在链表里的应用思路和数组完全一致但指针变成了节点指针空指针的判断要更小心。这三个方向都能在蓝桥杯真题里找到影子。尤其“三数之和”和“长度最小的子数组”一个是相向双指针的进阶一个是滑动窗口的进阶做会之后再看四道例题会有一种“原来是同一套底层逻辑”的感觉。最后分享一个备赛小组里常说的小技巧把四个例题的模板抄在纸上不要写代码只写“循环条件、左右指针移动规则、答案更新位置”这三行。每天睡前抽一分钟看一眼坚持一周。双指针题最怕的不是不会写而是把模板背死了。看这三行的过程其实是逼自己回顾“为什么指针要这么移”而不是“答案长什么样”。到考场上真正救你的永远是那些“为什么”。
阅读完成 · 觉得有帮助？
