如何用快慢指针原地移除元素、去重、移动零？

简化版

这类「原地修改数组」的题都用读写快慢指针:slow 指向「下一个要写入的位置」,fast 负责向前扫描。fast 遇到要保留的元素,就写到 slow 处、slow++;要丢弃的就跳过(只 fast++)。一趟 O(n) 就能原地重排,空间 O(1)。移除元素、有序数组去重、移动零、按条件过滤,都是这一个套路。

详细版

移除所有等于 val 的元素(返回新长度):

int removeElement(int[] a, int val) {
    int slow = 0;                        // 下一个写入位置
    for (int fast = 0; fast < a.length; fast++) {
        if (a[fast] != val) {            // 要保留的元素
            a[slow++] = a[fast];         // 写到 slow，slow 前进
        }
        // 等于 val 的跳过（只 fast 前进）
    }
    return slow;                          // [0, slow) 是结果
}

移动零(把所有 0 挪到末尾,保持非零相对顺序):

void moveZeroes(int[] a) {
    int slow = 0;
    for (int fast = 0; fast < a.length; fast++)
        if (a[fast] != 0) a[slow++] = a[fast];   // 非零前移
    while (slow < a.length) a[slow++] = 0;        // 剩余补 0
}

完整版教学

一、核心思想:读写分离

这类题的共同模式是「在原数组上,把该保留的元素紧凑地重新排到前面」。用两个指针分工:

fast(读指针):遍历整个数组,负责判断每个元素该不该保留。
slow(写指针):指向「下一个该写入的位置」,只有当 fast 遇到要保留的元素时,才把它写到 slow、slow++。

fast 一直前进,slow 只在保留时前进。遍历完,[0, slow) 就是筛选后的结果,slow 是新长度。因为直接在原数组上覆盖写入,不需要额外空间,O(1)。

二、为什么覆盖写入不会出错

有人担心「slow 处的原值被覆盖会不会丢」。不会——因为 slow 始终 ≤ fast(slow 前进速度 ≤ fast)。slow 要写入的位置,要么是已经处理过、可以安全覆盖的,要么就是 fast 自己(slow==fast 时自己覆盖自己,无害)。fast 永远走在 slow 前面或相同,所以「还没读的元素」绝不会被提前覆盖。这是读写指针成立的关键。

三、移除元素 / 移动零 / 去重是同一套

看似不同的题,本质都是「保留满足条件的元素、丢弃其余」:

移除元素:保留 != val 的。
移动零:保留 != 0 的(移到前面),末尾补 0。
有序数组去重:保留「和前一个不同」的(a[fast] != a[slow-1])。
删除排序数组中重复项 II(每个最多留 2 个):保留「和 a[slow-2] 不同」的。

只要把「保留条件」换掉,同一个 slow/fast 框架就能解一大类题。记住这个「slow 写、fast 读筛选」的模板。

四、有序数组去重的写法

int removeDuplicates(int[] a) {
    if (a.length == 0) return 0;
    int slow = 0;                        // [0, slow] 已去重
    for (int fast = 1; fast < a.length; fast++) {
        if (a[fast] != a[slow]) {        // 遇到新值
            a[++slow] = a[fast];         // slow 前进并写入
        }
    }
    return slow + 1;                      // 长度
}

因为有序,重复元素相邻,「和 a[slow] 不同」就是新值。这题的 slow 含义略变(指向「已去重区最后一个」),但思想一致。

五、为什么不要求「删除」的元素被清理

这类题通常只要求「前 slow 个是结果」,不关心 slow 之后残留什么。因为数组长度不可变,我们做的是「把有效元素压到前面」,后面的旧数据由调用方忽略(用返回的新长度截断)。这是「原地」的含义——不是真的删掉,而是重排 + 返回有效长度。

六、复杂度与要点

时间 O(n):fast 遍历一遍。
空间 O(1):原地覆盖,无额外数组。
要点:slow 是写指针(下一个写入位)、fast 是读指针(筛选);slow ≤ fast 保证不覆盖未读元素;换「保留条件」就能解不同题。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：slow 指向下一个写入位置，[0,slow) 始终是已保留元素的正确结果。

对应的状态推进是：fast 扫描原数据，满足保留条件时写到 slow 并递增。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。单次扫描 O(n)，写入次数不超过 n。

带数字走一遍：[0,1,0,3,12] 先压紧非零为 [1,3,12]，再把尾部填 0。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	适用于稳定保留；若允许改变顺序可用尾部交换减少写入
时间复杂度	O(n)
额外空间	O(1)
关键边界	返回新长度后尾部通常是未定义区域；移动零题才要求显式补零
替代方案	链表原地删除应改指针，不需要覆盖写入

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“适用于稳定保留；若允许改变顺序可用尾部交换减少写入”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“单次扫描 O(n)，写入次数不超过 n”。
误区：重复值和边界值不会改变代码。 返回新长度后尾部通常是未定义区域；移动零题才要求显式补零。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“slow 指向下一个写入位置，[0,slow) 始终是已保留元素的正确结果”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[0,1,0,3,12] 先压紧非零为 [1,3,12]，再把尾部填 0”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“链表原地删除应改指针，不需要覆盖写入”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

原地移除/去重/移动零都用读写快慢指针:slow 写(下一个写入位)、fast 读(遍历筛选),fast 遇到要保留的就 a[slow++]=a[fast],丢弃的跳过。一趟 O(n)、原地 O(1)。因 slow ≤ fast,覆盖写入不会丢未读元素。移除元素、移动零、去重(有序时「与前一个不同」)是同一套框架,只换「保留条件」。只保证前 slow 个是结果,后面残留不管。

简化版

详细版