值班刷题，第一个专题就是数组。以前很多次算法学习都死在起步阶段，这次换了个思路，不按顺序硬啃，而是按“数据结构 + 高频技巧”切块来打。数组是几乎所有数据结构的地基，双指针又是数组题里出现频率最高的一类解法，拿它当第一天再合适不过。
这篇笔记不打算写成题解堆砌，重点放在“为什么能用双指针”和“怎么从暴力解法一步步推到双指针”上。适合刚准备刷题、或者刷了一段时间但总觉得双指针用得不够顺的人。我自己也踩过不少边界条件的坑，写完顺手整理出来，算是给接下来的刷题计划打个好底子。
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，结果中间那个元素永远不会被处理。等想明白 left==right 时必须再处理一次，从那以后凡是双指针写完之后都会刻意检查一次边界条件。
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 明天的学习路线：双指针往滑动窗口延伸
双指针今天练的是两种基础的形态，但其实这个技巧家族还有第三副骨架——滑动窗口。它本质上还是双指针，只是窗口的右端负责扩展，左端负责收缩，两者配合起来维护一个可变长度的区间。数组题里“连续子数组”那类问题，基本都是滑动窗口的猎场。
明天的安排会在今天的快慢指针基础上，把“快指针扩展窗口、慢指针收缩窗口”这个新动作加进来。到时候你会发现，今天建立的快慢指针画面感，会成为理解滑动窗口的最大助力。这也是我今天坚持把状态图画清楚的原因，地基打牢一点，后面盖楼就快得多。
从数组到双指针再到滑动窗口，这条线走完，数组相关的高频题型基本上就覆盖了大半。第一步已经迈出去了，明天的滑动窗口，继续。
