算法刷题系列（十四）：移除元素——用读写指针原地筛选

算法刷题系列（十四）：移除元素——用读写指针原地筛选

上一章用相向双指针解决有序数组中的配对问题。本篇继续使用双指针，但两根指针不再从两端靠拢，而是同向前进：读指针检查每个元素，写指针记录下一个保留元素应该放置的位置。

这类读写指针常用于原地过滤、压缩重复元素和整理数组。关键不是“删除”物理单元，而是维护一个连续的有效前缀，并在遍历结束时返回它的长度。

一、题目与约定

给定数组 nums 和需要移除的值 target，把所有不等于 target 的元素移动到数组前部，并返回保留元素的数量。要求原地完成，不需要关心返回长度之后的内容。

例子：

nums = [3, 2, 2, 3], target = 3
结果长度 = 2
有效前缀 = [2, 2]

题目并不要求把数组缩短；数组长度仍为 4，只保证前两个位置是答案。

二、定义读写指针的不变量

遍历到下标 read 时，保持以下不变量：

nums[0..write) 恰好保存了已扫描部分中所有不等于 target 的元素，且顺序与原数组一致。

其中 write 指向有效前缀之后的第一个空位。每当读到一个应保留的值：

1. 把 nums[read] 写到 nums[write]；
2. write 前进一格。

每个元素最多读取一次、写入一次，所以时间复杂度为 O(n)，额外空间为 O(1)。

三、手动推演

初始：[3, 2, 2, 3]，write = 0
read=0：3 要移除，跳过
read=1：2 保留，写入 nums[0]，write = 1
read=2：2 保留，写入 nums[1]，write = 2
read=3：3 要移除，跳过
结束：返回 2，有效前缀为 [2, 2]

写入目标位置始终不晚于读取位置，因此不会覆盖尚未读取的数据。

四、Java 实现

public class RemoveElement {
    public static int removeElement(int[] nums, int target) {
        if (nums == null) {
            throw new IllegalArgumentException("nums must not be null");
        }

        int write = 0;
        for (int read = 0; read < nums.length; read++) {
            if (nums[read] != target) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }
}

五、Python 实现

def remove_element(nums: list[int], target: int) -> int:
    if nums is None:
        raise ValueError("nums must not be None")

    write = 0
    for read, value in enumerate(nums):
        if value != target:
            nums[write] = value
            write += 1
    return write

两种实现都保留了元素的相对顺序。如果题目允许改变顺序，可以用右端待检查元素填补被移除的位置，减少某些输入下的写入次数；不过那会改变稳定性，不能在未确认要求时擅自采用。

六、边界与测试

至少检查以下情况：

输入	目标值	返回长度	有效前缀
[]	1	0	[]
[1, 1]	1	0	[]
[1, 2, 3]	9	3	[1, 2, 3]
[3, 2, 2, 3]	3	2	[2, 2]

验证时只比较有效前缀，不要检查数组尾部是否清零或删除；尾部内容不属于题目保证的输出。

七、常见错误

1. 写指针每轮都前进：只有保留元素时才增加 write。
2. 返回数组容量：应返回保留数量 write，不是原数组长度。
3. 清理有效前缀之后的元素：通常既无必要，也会增加操作。
4. 错误地从 read + 1 开始写：写指针描述有效前缀末尾，不是读指针的副本。
5. 迭代器遍历同时结构性删除：数组题用读写位置更直接，也能清楚证明不会跳过元素。

八、与后续主题的连接

本题通过一次扫描维护前缀状态。若关注的不是单个元素，而是一个区间的总和，可以把“扫描到当前位置为止的累计值”保存下来。下一篇将用前缀和把区间求和转化为两个前缀值之差，并进一步结合哈希表统计满足目标的子数组。

小结

原地筛选的核心是有效前缀不变量：读指针负责判断，写指针负责紧凑地保存保留值。遍历结束时，写指针正好等于答案长度。确认题目是否要求稳定顺序，并只读取返回长度以内的数组内容。