数组双指针：原地修改数组的核心范式
摘要
“原地修改数组”是面试中频率极高的一类题型，要求在不使用额外数组的前提下，对数组进行过滤、去重或删除操作。本文以 LeetCode 26、80、27 三道经典题为切入点，深入推导**同向双指针（快慢指针）**的设计逻辑——不是告诉你”用双指针”，而是从约束出发，一步步推导出为什么这个方法是必然选择。理解本篇后，你将掌握一个可以覆盖大量数组变体题的核心范式。
第 1 章 从约束出发：为什么不能开新数组
1.1 题目约束的本质
先看 LeetCode 26 的题目要求：
给你一个升序排列的数组
nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 额外空间的条件下完成。
“不要使用额外的数组空间”和” 额外空间”——这两个约束是解题方向的关键。
面对这道题，很多人的第一直觉是：
- 开一个新数组
result，遍历nums，把不重复的元素塞进去 - 把
result复制回nums
这当然是对的，逻辑也很清晰。但题目明确禁止了这条路，因为它需要 的额外空间。
那么，在”不能另开空间”这个铁约束下，我们只能在原数组上动刀。原数组是一块固定的内存，我们能做的只有读取和覆写。思路就此收敛：用原数组的前半部分存放结果，用原数组的后半部分当作”待处理区”，同时推进两个位置指针。
1.2 双指针的必然性
想象你是一个邮差，手里有一摞信件（原数组），里面有些重复的。你的任务是把不重复的信件整理好叠放在桌子左侧（原数组前段），不允许另找一张桌子。
你需要两只手：
- 左手（慢指针
slow）：维护”已整理好的区域”的边界，指向下一个可以安全写入的位置 - 右手（快指针
fast）：逐一检查每封信件，判断它是否值得放入已整理区域
这就是双指针的本质：两个指针各司其职，一个负责”写”，一个负责”读”，通过不同的移动速度完成原地筛选。
设计哲学：双指针的不变量
优秀的双指针代码背后都有一个循环不变量（Loop Invariant），即在每次循环迭代结束后，始终成立的性质。对于这类”原地过滤”的双指针来说，不变量是：
nums[0..slow-1]区间内的元素，始终是已处理好的满足条件的结果集合。 理解了不变量，边界条件就不再靠直觉，而有严格的逻辑支撑。
第 2 章 LeetCode 26：删除有序数组中的重复项
2.1 题目
LeetCode 26 - Remove Duplicates from Sorted Array（简单）
给你一个升序排列的数组 nums，请原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。
示例：
输入: nums = [1,1,2]
输出: 2, nums = [1,2,_]
解释: 函数应该返回新的长度 2，并且原数组 nums 的前两个元素被修改为 1, 2
输入: nums = [0,0,1,1,1,2,2,3,3,4]
输出: 5, nums = [0,1,2,3,4,_,_,_,_,_]
2.2 思路推导
关键前提：数组已升序排列。
这个前提至关重要，正因为数组有序，所有相同的元素一定紧挨在一起。因此，判断一个元素是否”重复”只需要和前一个元素比较，不需要全局查找。
现在用双指针框架来思考：
初始状态：slow = 1（下标从 1 开始，因为第一个元素永远不是重复的，直接保留），fast = 1
循环体的逻辑：
- 如果
nums[fast] == nums[slow-1]：fast指向的元素和已保留区域的最后一个元素相同，是重复的，跳过（只移动fast） - 如果
nums[fast] != nums[slow-1]：fast指向的是新值，写入slow位置，slow++，然后fast++
为什么和 nums[slow-1] 比较而不是 nums[slow]？
因为 slow 指向的是”下一个可写位置”，slow-1 才是”已保留区域的最后一个元素”。这个细节是初学者最容易混淆的地方，理解不变量就能自然得出这个结论。
手动模拟（以 [0,0,1,1,1,2,2,3,3,4] 为例）：
初始: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
^slow=1 ^fast=1
step1: nums[fast=0] == nums[slow-1=0] → 重复，fast++
[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
^slow=1 ^fast=2
step2: nums[fast=1] != nums[slow-1=0] → 新值，写入 nums[slow]=nums[fast], slow++, fast++
[0, 1, 1, 1, 1, 2, 2, 3, 3, 4]
^slow=2 ^fast=3
step3: nums[fast=1] == nums[slow-1=1] → 重复，fast++
...（类似地跳过连续的 1）
最终: [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
^slow=5
返回: slow = 5
前 slow 个元素就是去重后的结果，后面的元素不用管（题目也不要求清零）。
2.3 代码实现
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 1; // slow 指向下一个可写位置，nums[0..slow-1] 是已处理好的结果
for (int fast = 1; fast < nums.length; fast++) {
// nums[fast] 和已保留区域的最后一个元素比较
if (nums[fast] != nums[slow - 1]) {
// 发现新值，写入 slow 位置
nums[slow] = nums[fast];
slow++;
}
// 如果相等，fast 继续推进，slow 不动（等待下一个新值）
}
return slow; // 结果数组的长度
}复杂度分析：
- 时间：，
fast从头到尾扫描一遍，每个元素最多被访问 2 次（一次读、一次可能的写） - 空间：，只用了两个指针变量，符合题目要求
2.4 边界条件
- 空数组：
nums.length == 0，直接返回 0，需要特判（否则slow = 1，for循环不会执行，但返回slow = 1是错误的） - 长度为 1 的数组：
slow = 1，for循环不执行，返回 1，正确 - 全部相同如
[1,1,1]：slow始终停在 1，fast走到底，最终返回 1，正确
第 3 章 LeetCode 80：删除有序数组中的重复项 II
3.1 题目
LeetCode 80 - Remove Duplicates from Sorted Array II（中等）
与第 26 题几乎相同，区别只有一点：每个元素最多保留两次（而不是一次）。
输入: nums = [1,1,1,2,2,3]
输出: 5, nums = [1,1,2,2,3,_]
输入: nums = [0,0,1,1,1,1,2,3,3]
输出: 7, nums = [0,0,1,1,2,3,3,_,_]
3.2 从第 26 题泛化：保留 k 次的通用模板
这道题是第 26 题的自然延伸，设计上非常优雅，值得细细体会。
第 26 题的约束：每个元素最多保留 1 次 → 比较 nums[fast] 和已保留区域的倒数第 1 个元素
第 80 题的约束：每个元素最多保留 2 次 → 比较 nums[fast] 和已保留区域的倒数第 2 个元素
规律一目了然：如果要每个元素最多保留 次，就比较 nums[fast] 和 nums[slow - k]。
为什么？
如果 nums[fast] == nums[slow - k]，说明什么？
当前已保留区域的最后 个元素（下标 slow-k 到 slow-1）全部等于 nums[fast]（因为数组有序，相同元素连续，如果倒数第 个都等于当前值，那倒数第 、…第 1 个都等于当前值）。这意味着如果再加入 nums[fast]，这个值就出现了 次，超出了限制，应该跳过。
如果 nums[fast] != nums[slow - k]，说明倒数第 个位置的元素不等于当前值，当前值出现次数还没满 次，可以放入。
这就是所谓的”泛化”：同一个框架，改变一个参数 ，就能解决”最多保留 k 次”这一类题。
3.3 代码实现
public int removeDuplicates(int[] nums) {
// k=2 的特化版本，slow 从 2 开始（前两个元素直接保留）
if (nums.length <= 2) return nums.length;
int slow = 2; // 每个元素最多保留 2 次，前 2 个直接保留
for (int fast = 2; fast < nums.length; fast++) {
// 比较 nums[fast] 和已保留区域的倒数第 2 个元素（下标 slow-2）
if (nums[fast] != nums[slow - 2]) {
nums[slow] = nums[fast];
slow++;
}
// 如果相等，说明当前值已经出现 ≥2 次，跳过
}
return slow;
}手动验证 [1,1,1,2,2,3]：
初始: slow=2, fast=2
[1, 1, 1, 2, 2, 3]
^slow=2 ^fast=2
step1: nums[fast=2]=1, nums[slow-2=0]=1 → 相等，跳过，fast++
step2: nums[fast=3]=2, nums[slow-2=0]=1 → 不等，写入 nums[2]=2, slow=3, fast=4
[1, 1, 2, 2, 2, 3]
^slow=3 ^fast=4
step3: nums[fast=4]=2, nums[slow-2=1]=1 → 不等，写入 nums[3]=2, slow=4, fast=5
[1, 1, 2, 2, 2, 3]
^slow=4 ^fast=5
step4: nums[fast=5]=3, nums[slow-2=2]=2 → 不等，写入 nums[4]=3, slow=5
[1, 1, 2, 2, 3, 3]
^slow=5
返回: 5
结果 [1,1,2,2,3]，正确。
3.4 通用模板（保留 k 次）
// 通用模板：保留每个元素最多 k 次
public int removeDuplicates(int[] nums, int k) {
int slow = k;
for (int fast = k; fast < nums.length; fast++) {
if (nums[fast] != nums[slow - k]) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}这个模板是双指针范式优雅的体现：一个参数的变化，解决了一整类问题。面试时如果你能主动给出通用模板，会给面试官留下深刻印象。
第 4 章 LeetCode 27：移除元素
4.1 题目
LeetCode 27 - Remove Element（简单）
给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，必须仅使用 额外空间并原地修改输入数组。
输入: nums = [3,2,2,3], val = 3
输出: 2, nums = [2,2,_,_]
输入: nums = [0,1,2,2,3,0,4,2], val = 2
输出: 5, nums = [0,1,4,0,3,_,_,_]（顺序可以改变）
注意：和第 26 题不同，这里的数组不一定有序，可以是任意顺序。
4.2 方法一：同向双指针（与第 26 题一脉相承）
最直接的思路：slow 指向可写位置，fast 扫描每个元素，遇到不等于 val 的就写入 slow。
public int removeElement(int[] nums, int val) {
int slow = 0; // slow 指向下一个可写位置
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != val) {
// 不是目标值，保留到 slow 位置
nums[slow] = nums[fast];
slow++;
}
// 等于 val 则跳过（fast++ 由 for 循环自动完成）
}
return slow;
}复杂度：时间 ，空间 。
这个方法保留了原始元素的相对顺序，这在某些题目中是必要的。但注意：题目说了”顺序可以改变”，这意味着有更优化的方案。
4.3 方法二：对撞双指针（减少元素移动次数）
方法一的问题在于：即使 val 出现次数极少（比如只有 1 次），我们仍然会把所有其他元素都”复制”一遍（nums[slow] = nums[fast] 会执行 次）。
如果允许改变顺序，有一个更聪明的方案：用一个左指针从头扫，遇到 val 就用右指针指向的末尾元素覆盖，然后右指针左缩。
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
if (nums[left] == val) {
// 用末尾元素覆盖当前 val，右指针左缩
// 注意：不能立刻 left++，因为覆盖过来的末尾元素可能也等于 val，需要再检查
nums[left] = nums[right];
right--;
} else {
left++;
}
}
return left; // left 就是有效元素的数量
}手动模拟 [3, 2, 2, 3], val=3：
left=0, right=3
nums[0]=3 == val → 用 nums[3]=3 覆盖 nums[0]，right=2
[3, 2, 2, 3] → [3, 2, 2, 3]（数组内容暂时没变，但 right 左移了）
left=0, right=2
nums[0]=3 == val → 用 nums[2]=2 覆盖 nums[0]，right=1
[3, 2, 2, 3] → [2, 2, 2, 3]
left=0, right=1
nums[0]=2 != val → left++
left=1, right=1
nums[1]=2 != val → left++
left=2, right=1 → left > right，退出循环
返回: left = 2
对撞双指针的优势：当 val 出现次数很少时，只需要少量的覆盖操作。假设数组长 ，只有 个 val，那么只需要 次覆盖，而同向双指针需要 次复制。当 时，对撞双指针更高效。
何时选同向，何时选对撞？
- 同向双指针：需要保留元素的原始相对顺序时（如 LeetCode 26、80），或者判断逻辑依赖已处理区域的状态时
- 对撞双指针：允许改变顺序，且希望减少实际的内存写操作次数时（如本题方法二）；另一个常见场景是有序数组的两数之和（找两端夹逼）
第 5 章 双指针的更多变体与延伸思考
5.1 “读写分离”的本质
回顾三道题，双指针范式的核心逻辑可以用一句话概括：
slow（写指针）只在”值得保留”时才推进，fast（读指针）每次都推进。 两者的速度差形成了一个”筛选漏斗”——通过条件的元素被slow收入囊中，不通过的被fast直接越过。
这种”读写分离”的思想，在很多数组题中反复出现，是一种非常通用的范式。
5.2 有序 vs 无序对算法的影响
| 题目 | 数组状态 | 判重方式 | 为什么可以这样判重 |
|---|---|---|---|
| LeetCode 26（去重，最多1次） | 有序 | 与 nums[slow-1] 比较 | 有序保证相同元素相邻，只需比前一个 |
| LeetCode 80（去重，最多2次） | 有序 | 与 nums[slow-2] 比较 | 同上，泛化到 k 次 |
| LeetCode 27（移除指定值） | 无序 | 直接与 val 比较 | 判断条件是绝对值，不依赖相邻关系 |
如果第 26 题的数组是无序的，双指针还够用吗？不够，需要借助哈希表来判断一个元素是否已经出现过，代价从 升为 空间。有序性是很多线性扫描算法的前提，在面试中看到”升序数组”、“已排序”这类描述，要立刻意识到它开放了很多高效算法的可能性。
5.3 这类题的面试应对策略
遇到数组的”原地过滤/修改”类题目，标准思路：
- 确认是否允许额外空间：如果允许，用新数组最简单；如果不允许，走双指针路线
- 确认是否需要保持顺序：不需要则可考虑对撞双指针，减少写操作
- 明确不变量：在写代码前，确定”在任意时刻，
nums[0..slow-1]保存的是什么” - 检查边界：空数组、单元素、全部是目标值、全部不是目标值
5.4 与排序的结合
有时候原数组无序，但题目允许先排序再处理。排序的代价是 ，但如果排序后可以用 的双指针解决，总体仍然是 ，往往比 的暴力解法好得多。
这是后续第 5 篇05 多指针夹逼：3Sum、3Sum Closest、4Sum 系列的核心策略：先排序，然后双指针夹逼。
第 6 章 代码模板总结
为了便于复习，把本篇的核心模板整理如下：
模板一：同向双指针（保留非 val 元素，维持顺序）
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (符合保留条件) {
nums[slow++] = nums[fast];
}
}
return slow;模板二：有序数组去重（最多保留 k 次）
int slow = k;
for (int fast = k; fast < nums.length; fast++) {
if (nums[fast] != nums[slow - k]) {
nums[slow++] = nums[fast];
}
}
return slow;模板三：对撞双指针（允许改变顺序，用末尾覆盖）
int left = 0, right = nums.length - 1;
while (left <= right) {
if (nums[left] == val) {
nums[left] = nums[right--];
// 注意：不 left++，需要重新检查当前 left 位置
} else {
left++;
}
}
return left;第 7 章 常见错误与陷阱
7.1 slow 初始值设错
错误示例：
// LeetCode 26 的错误写法
int slow = 0; // 错：slow 应该从 1 开始
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) { // 此时 slow=0，第一个元素和自己比？
nums[++slow] = nums[fast]; // ++slow 是先加后用，还是 slow++ 先用后加？
}
}问题：slow = 0 时，第一次进入循环，nums[fast=1] 和 nums[slow=0] 比较，如果相等，slow 不动，nums[slow=0] 始终指着第一个元素，逻辑上是对的。但如果用 nums[++slow] = nums[fast]（先加再写），第一次写是写到 nums[1]，而 nums[0] 已经是正确的第一个元素，这样也对。
但这种写法容易混淆先加和后加，且不如 slow=1 的写法直观。推荐始终使用”slow 指向下一个可写位置”的语义，而不是”slow 指向已写入的最后一个位置”，前者代码更简洁。
7.2 对撞双指针的自我覆盖问题
// 对撞双指针，当 left == right 时
if (nums[left] == val) {
nums[left] = nums[right]; // 用 nums[right] 覆盖 nums[left]
right--;
}
// 如果 nums[right] 和 nums[left] 指向同一个位置且都等于 val，
// 这里 nums[left] = nums[right] 是自我覆盖，不会出错（结果还是 val）
// 但 right-- 后，left > right，循环结束，这个 val 没有被跳过！等一下，真的有问题吗？让我们分析：当 left == right 且 nums[left] == val，执行 nums[left] = nums[right]（自我赋值，无害），然后 right--，此时 right < left，循环退出，返回 left。此时 nums[left] 这个位置是 val，但返回值 left 表示有效长度，nums[left] 已经在范围外，所以实际上是正确的——这个 val 被”排除在外”了（虽然内存上它还在，但返回的长度不包含它）。
7.3 for-each 和下标的混用
// 错误：for-each 不给你下标，无法用作 slow/fast 指针
for (int num : nums) {
// 不知道 num 在哪里，无法进行 nums[slow] = num 操作
}双指针题必须用下标索引遍历，不能用 for-each 语法。
下一篇预告
03 数组二分搜索变体：旋转数组与中位数 将进入二分搜索的深水区。二分查找的”找某个值”大家都会，但”在旋转有序数组里搜索”和”找两个有序数组的中位数”是面试的高频难点。我们会从二分的核心思想——每次排除一半搜索空间——出发，建立应对所有二分变体题的通用框架。