值班刷题第一个专题就是数组。以前很多次算法学习都死在起步阶段这次换了个思路不按顺序硬啃而是按“数据结构 高频技巧”切块来打。数组是几乎所有数据结构的地基双指针又是数组题里出现频率最高的一类解法拿它当第一天再合适不过。这篇笔记不打算写成题解堆砌重点放在“为什么能用双指针”和“怎么从暴力解法一步步推到双指针”上。适合刚准备刷题、或者刷了一段时间但总觉得双指针用得不够顺的人。我自己也踩过不少边界条件的坑写完顺手整理出来算是给接下来的刷题计划打个好底子。1. 数组这个结构为什么值得单独花一天1.1 连续内存带来的三个隐藏约束数组最本质的特征是连续内存 随机访问。初学的时候觉得这太简单了不就是一个排排坐的格子嘛。但真正做题的时候连续内存衍生出来的三个特性几乎决定了所有题目策略第一步索引就是地址偏移。数组访问的时间复杂度是 O(1)遍历一遍是 O(n)这谁都知道。但更关键的是正因为内存连续我们才能用“指针/下标”这种抽象去描述位置并且能同时维护多个位置。双指针的一切基础都在这里。第二步插入和删除是有代价的。在数组中间删掉一个元素不是简单地把那个格子清空而是要把后面所有元素往前挪一位。在线性存储里删除最坏是 O(n)。很多数组题的核心矛盾其实就是“我想删/想换但每次动都是 O(n)怎么少动几次”。第三步数组长度固定但题目经常要求原地操作。原地两个字一出来就不能开新数组痛快地做得在一个数组里倒腾。这时候“从后往前填”“左右交换”这类操作自然就成了高频手段。1.2 为什么第一次刷题容易被“简单题”卡住数组在教科书里太基础了很多人的误区是直接用“数据结构难度”来判断题目难度。实际刷题的时候会发现数组题难的不是数据结构的理解而是题目条件之间的互相制约。举个例子给你一个有序数组要求把重复元素去重并且原地修改最后返回新长度。看起来很直接对不对但你一旦原地删for 循环的索引就会乱越界问题立刻冒出来。这种“循环变量在动数组也在动”的双重变化是新手最容易懵的地方。传统解法是用一个独立计数器去记录有效位置然后用这个计数器作为写入索引。等写顺手了再回头看这不就是快慢指针吗所以数组题的第一课我觉得本质上就是学会用下标来管理状态而不是让循环变量同时干太多事。2. 双指针的两种基本骨架快慢与对撞2.1 快慢指针一种“延迟写入”的思路快慢指针最常见的应用场景是原地过滤。想象一下你要从数组里挑出符合条件的元素并且把它们按顺序放在前面。如果开一个新数组那就是遍历原数组逐个 append。但不能开新数组的时候怎么办一个很自然的替代方案是用慢指针指向“下一个可以写入的位置”用快指针负责扫描全数组。快指针找到合格元素就往慢指针的位置写然后慢指针前进一步。这个思路的精髓在于把“找”和“写”解耦了。快指针干循环的活慢指针记录结果长度。两个指针互不干扰所以再也不会出现“删掉一个元素后索引越界”的问题。很多初学者觉得双指针高深其实第一步就是把这两个职责分开。慢指针还有一个很妙的特性它最终停下来的位置恰恰就是结果的长度。这就是为什么这类题经常让你“原地修改并返回新长度”——答案一直在你手边。2.2 对撞指针利用数组的顺序信息对撞指针的核心场景是数组本身有序。一根指针从头往右走一根从尾往左走两个指针向中间靠拢。这种写法充分利用了有序信息左边是当前最小值所在区域右边是当前最大值所在区域。要做的事往往是“比较两边大小决定哪边先落位”。最典型的就是“有序数组的平方”这类题。原数组有序但负数平方之后大小顺序会被打乱。暴力做法是先算平方再排序O(n log n)。用对撞指针呢因为原数组有序平方后最大的数一定出现在两端——要么是最左边的负数平方要么是最右边的正数平方。于是两个指针谁大谁先放到结果数组的末尾一趟走完就是 O(n)。对撞指针的命名我自己其实不太喜欢叫“两端指针”可能更好理解。但刷题社区里对撞这个词用得多记住就行。它和快慢的最大区别是快慢是同向的对撞是相向的千万别混。2.3 两道骨架分别怎么判断判断一道题该用哪个我自己的经验是问两个问题需要保留相对顺序、原地过滤→ 快慢指针。充分利用已有顺序、两边往中间靠→ 对撞指针。这两条不是死规则但作为第一天的判断框架够用了。后面刷多了会发现很多题是两种结合比如对撞的过程中其实内层还在做快慢过滤不过那是后话。3. 从暴力解法推导到双指针的完整过程3.1 经典场景A移除指定元素有一段数组里面有目标值要求原地删掉所有目标值返回新长度。我最初看到这道题的第一反应是写一个循环遇到目标值就把后面的元素整体往前挪。这样写确实能过但每次删除都是 O(n)最坏情况下数组里全是目标值那就成了 O(n²)。代码很简单测试也能过但这道题想考的东西你完全没碰到。换一个角度我们不关注“删掉了什么”我们只关注“留下了什么”。留下来的元素需要按原序排列在数组前面空间完全够用。于是用慢指针指向待写入位置快指针扫描快指针遇到非目标值就写到慢指针位置慢指针加一快指针遇到目标值跳过什么都不管。这样扫一遍下来前面的位置被有效元素覆盖满慢指针的位置就是新长度。代码量比暴力版本少复杂度还从 O(n²) 降到 O(n)。这个推导过程其实是双指针最标准的思维路径先想“结果长什么样”再想“怎么把结果在原来的空间里堆出来”最后用两个指针把读写职责分开。给出一个可运行版本语言用的是 Go思路在所有语言里通用func removeElement(nums []int, val int) int { slow : 0 for fast : 0; fast len(nums); fast { if nums[fast] ! val { nums[slow] nums[fast] slow } } return slow }3.2 经典场景B有序数组的平方题目是给你一个非递减排序的数组包含负数要求返回每个数平方之后组成的新数组并且也是非递减排序。暴力解法是平方之后排序。但既然题目强调数组本来就是有序的我们就要想想怎么利用这个有序性。平方之后最大的数一定来自两端这个结论前面已经推导过。那我们就从两端往中间推进比较左指针指向数的平方和右指针指向数的平方大的那个放到结果数组的最后一个空位对应指针向中间移动一步继续比较。为什么从后往前填因为我们在从大到小地确定答案。如果从前往后填就得先找出最小的平方数而最小值可能在中间某个位置确定起来麻烦。从两端向中间取最大正好和“结果数组从后往前填”对齐。func sortedSquares(nums []int) []int { n : len(nums) res : make([]int, n) left, right : 0, n-1 pos : n - 1 for left right { l2, r2 : nums[left]*nums[left], nums[right]*nums[right] if l2 r2 { res[pos] l2 left } else { res[pos] r2 right-- } pos-- } return res }这道题我犯过的错误是循环结束条件写成了left right结果中间那个元素永远不会被处理。等想明白 leftright 时必须再处理一次从那以后凡是双指针写完之后都会刻意检查一次边界条件。4. 同套路变体移动零与反转字符串4.1 移动零快慢指针的一个小变形“把数组里的 0 全部移到末尾同时保持非零元素的相对顺序”这道题是第一道题的亲兄弟。区别在于第一道题是“删掉目标值”这里是“把目标值移到后面”。处理方式非常顺滑先用快慢指针对非零元素做过滤把它们全部堆到前面接着从慢指针位置开始把后面剩余位置全部填成 0。之前你可能觉得“把 0 移到后面”需要真的去交换元素。其实不需要。先在原地把非零元素归位再统一补 0效果完全一样代码还更好写。这算是对“结果是啥样”这个思维的第二次实践你要的不是移动过程而是最终状态。func moveZeroes(nums []int) { slow : 0 for fast : 0; fast len(nums); fast { if nums[fast] ! 0 { nums[slow] nums[fast] slow } } for i : slow; i len(nums); i { nums[i] 0 } }这个问题还有另一种写法遇到非零元素就和非零位置交换过程里就会把 0 慢慢“顶”到后面去。两种都能过但第一种写法更好解释也更容易往其他题型迁移我建议新手先用这种。4.2 反转字符串对撞指针的第一课反转数组算是最朴素的对撞指针应用了。左指针指向开头右指针指向结尾交换两个位置的值然后左指针右移、右指针左移直到两者相遇。这道题简单到几乎所有教材都会提但它是理解对撞指针最好的热身两个指针之间的位置关系是“中间状态”交换之后两边都往中间收缩每次操作都在缩小未处理区间。很多人在反转字符串的时候会想直接倒着遍历生成新字符串不就行了吗是行但题目要求原地修改而且对撞指针的操作次数是 n/2比开新数组更省空间。这类题的训练价值其实不在“会不会写”而在于让你适应“用两个下标把一个区间夹出来”的思考方式。func reverseString(s []byte) { left, right : 0, len(s)-1 for left right { s[left], s[right] s[right], s[left] left right-- } }4.3 为什么做变体题比做新题更重要我自己的切身体会刷题最容易出现的假象是看题解觉得懂了换一道同类的又不会了。原因就在于看题解时只记住了代码没有记住“题目结构和解法结构之间的映射”。同一个套路做三道变体题比做三道完全不同类型的题收获更大。因为第一道建立基本写法第二道开始认知变形第三道才真正把套路内化。移动零和反转字符串就是为这个目的准备的一道快慢变体一道对撞入门合起来把双指针的两副骨架都练了一遍。5. 双指针的边界条件一天下来踩过的坑全记录5.1 空数组和单元素数组空数组必须直接返回 0这个如果不单独处理len(nums)-1 会得到 -1直接越界。单元素数组稍微隐蔽一点比如那个反转字符串的循环条件是left right单元素时两个指针相等循环不进自然就不用交换这是对的。但有些题目里单元素会引发“结果数组位置不对”的问题比如有序数组平方那道题如果在循环条件里用了left right单元素就直接漏处理了。我现在的习惯是写完双指针代码第一个用空数组跑第二个用单个元素跑第三个用全部相同的元素跑。三组数据过了边界问题基本能挡掉一大半。5.2 循环结束条件到底写还是这是今天踩得最多的地方。快慢指针的同向循环基本都用因为快指针遍历完就结束了。对撞指针就要看情况如果是“双方比较大小直到一方越界”通常用如果是“双方都必须被处理到相遇为止”通常用。一个比较容易记的口诀是看中间那个元素是不是也有资格被处理。如果左右指针相遇时指向的那个元素还没被任何一步逻辑处理过就必须用再进一次循环如果每一步逻辑都把指针推进到新位置那么相遇时的元素已经在某次迭代里被覆盖了用就够。5.3 原地覆盖会不会把还没读的数据弄丢移除元素那道题慢指针写入的位置一定在快指针已经扫描过的区域内所以覆盖是安全的。这个关系要自己想明白否则总担心“把后面的数据冲掉了”。直觉上可以这样理解快指针永远走在慢指针前面或者并列慢指针指向的位置只有两种可能要么是已经处理完的旧值要么就是快指针之前路过时留下的有效值。无论哪种覆盖它都不影响后续判断。但如果哪天你的慢指针跑到了快指针前面那就一定出 bug 了这可以作为双指针题目调试时的一个检查点。5.4 多指针时别共用同一个变量名我犯过的另一个离谱问题是在一个循环里同时维护左指针和“写入位置”图省事用了同一个变量。结果代码逻辑上完全跑不通调了半天才发现是两个职责被混在一起了。双指针题目的本质是“多个状态同时推进”每根指针有自己独立的变化节奏千万不要为了省变量而强行合并。慢指针的步进节奏是“写入一次才动一次”快指针是“每遍历一个元素动一次”两者节奏天然不同合并后肯定会乱。6. 第一天的沉淀怎么把双指针变成一种本能6.1 从“背模板”到“画状态图”今天最大的方法论收获是发现双指针题写不出来的时候与其看题解不如在草稿纸上画状态图。画一个数组格子把慢指针、快指针分别标出来手动走两三轮。你会发现规律自己就浮现了快指针经过的位置已经被处理慢指针之前的位置是最终结果两者夹着的灰色地带是还没处理的区域。这个画面一旦在脑子里形成了代码怎么写只是翻译问题而已。我之前写双指针总是不放心就是因为脑子里没有这张图。抽象地想“快慢指针”永远觉得玄画出来之后每一步的逻辑都是清清楚楚的。6.2 题目分类比题目数量更重要刷题圈里经常比谁刷得多但以我的体验来看做题质量的关键在于能不能把一道题归类到已经会的方法里。比如移除元素和移动零本质都是快慢过滤只是过滤后对剩余区域的处理不同反转字符串和有序数组平方本质都是对撞收缩只是收缩时交换还是比较大小的区别。这个分类的颗粒度不需要很细先分到“快慢”“对撞”两堆就够了。遇到新题先问自己它像哪个骨架再动手写。你会发现很多所谓新题不过是旧骨架换了一层新壳。6.3 明天的学习路线双指针往滑动窗口延伸双指针今天练的是两种基础的形态但其实这个技巧家族还有第三副骨架——滑动窗口。它本质上还是双指针只是窗口的右端负责扩展左端负责收缩两者配合起来维护一个可变长度的区间。数组题里“连续子数组”那类问题基本都是滑动窗口的猎场。明天的安排会在今天的快慢指针基础上把“快指针扩展窗口、慢指针收缩窗口”这个新动作加进来。到时候你会发现今天建立的快慢指针画面感会成为理解滑动窗口的最大助力。这也是我今天坚持把状态图画清楚的原因地基打牢一点后面盖楼就快得多。从数组到双指针再到滑动窗口这条线走完数组相关的高频题型基本上就覆盖了大半。第一步已经迈出去了明天的滑动窗口继续。