顺序表原地删除指定元素：双指针一趟搬移

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。原地删除指定元素是「顺序表」这一考点里最基础的原地操作，双指针「慢指针只写有效值」的模式贯穿了顺序表的大量题目。它是经典训练题，不是真题，也不押题。

题目

给定一个顺序表（数组）nums 和一个整数 val，要求原地删除所有值等于 val 的元素，返回删除后顺序表的新长度。不要求保持剩余元素原来的相对顺序以外的额外约束，也不允许使用额外数组。例如 nums = [3, 2, 2, 3]、val = 3，删除后 nums 的有效部分应为 [2, 2]（新长度 2），nums 中新长度之后的元素值不作要求。

这道题没有「尽可能高效」的要求。按拓展训练导语的分类，它属于「直观即满分」型——直白写法就是最优解，力气花在把「原地」这两个字落到实处。

直观解法：双指针一趟搬移

「原地删除」在顺序表上有一个标准动作：快指针负责逐个体检，慢指针负责收纳合格品。快指针 fast 从头到尾扫一遍数组的每个元素；每当 nums[fast] 不等于 val（合格），就把它写到 nums[slow] 的位置，然后慢指针前进一步。扫描结束后，慢指针的值就是新长度——nums[0..slow-1] 正是删除 val 后剩下的所有元素。

int removeElement(int nums[], int n, int val) {
    int slow = 0;
    for (int fast = 0; fast < n; fast++) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];   // 只有非目标元素才写入 slow 位置
            slow++;
        }
    }
    return slow;                       // slow 就是新长度
}

拿 nums = [3, 2, 2, 3]、val = 3 走一遍：fast=0，nums[0]=3 等于 val，跳过，slow 不动；fast=1，nums[1]=2 不等于 val，写 nums[0]=2，slow 变成 1；fast=2，nums[2]=2 不等于 val，写 nums[1]=2，slow 变成 2；fast=3，nums[3]=3 等于 val，跳过。扫描结束，slow=2，nums[0..1] = [2, 2] ✓。

复杂度：fast 从头到尾扫一遍数组，时间 $O (n)$ ；只用了 slow、fast 两个下标，没有额外数组，空间 $O (1)$ 。

为什么它就是满分解

用总纲的「找浪费三问」审一遍，三问全部答「没有」：

有没有重复扫描？ 没有。fast 只从左到右扫一遍，每个元素只被检查一次，不需要回头重新体检。
有没有重算已知的东西？ 没有。每个元素是否等于 val 是独立判断，不依赖之前的检查结果，没有可以省略的重复计算。
有没有放着性质不用？ 这道题没有额外的性质（比如有序性）可用——它靠的是「原地」这个约束本身给出的解法方向：既然不能用额外数组，双指针同向扫描、慢指针只写合格品，就是把「过滤」这个操作压缩进一次遍历的标准做法。

更根本的一条：判断每个元素是否等于 val、并把不等于的元素归位，至少要把数组看一遍——读一遍数组就是 $O (n)$ 的下界，任何正确算法都躲不开。碰到下界，就没有优化空间，直观写法即最优。

真正的难点在这里

分不在优化上，在把双指针的语义写准：

慢指针只在「写入」时前进，快指针无条件前进。这是这类双指针题的通用模式：fast 负责遍历全部元素（体检），slow 负责记录已经确认合格的元素数量（收纳）。把这两个职责分清楚，循环体只有一行有效写入，逻辑不会绕。
nums[slow] = nums[fast] 在 slow == fast 时是无害的自我赋值，不需要为了「省一次多余赋值」额外加判断——那样反而让代码更绕，且对时间复杂度没有实质帮助。
返回值是新长度，不是布尔值或删除个数。调用方后续应当只访问 nums[0..返回值-1]，新长度之后的元素内容不作规定（可能保留旧值，也可能被覆盖），这是题面里「不要求保持除此以外的约束」的具体含义。
不要求保持顺序之外的任何东西，但这份实现顺手保持了相对顺序——nums[slow] = nums[fast] 是按 fast 递增的顺序写入的，天然保持了非目标元素原有的相对顺序，这是免费获得的副产物，不是额外要求。

一趟搬移,看一遍

用 nums = [3, 2, 2, 3]、val = 3 演示——慢指针只在遇到非 3 的元素时前进并写入：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

别画蛇添足

这道题结构简单,过度设计的空间不大,但有两个常见的「想复杂了」：

想开一个新数组收集非目标元素，再拷贝回原数组。这违反了「原地」的要求——额外数组把空间从 $O (1)$ 拉到 $O (n)$ ，而双指针本来就能在原数组上一趟完成，不需要这份额外空间。
想先统计目标元素出现次数，再统一搬移。多这一趟统计并不能减少后续搬移的工作量，反而把一趟能做完的事拆成了两趟，时间常数变大却没有换来任何好处。

下一步

看顺序表基础操作的交互演示：顺序表可视化
回到方法论源头：「暴力解到最优解」真题专题总纲
同属顺序表双指针模式的真题：2013·41 主元素、2018·41 未出现的最小正整数

顺序表原地删除指定元素：双指针一趟搬移 ​

题目 ​

直观解法：双指针一趟搬移 ​

为什么它就是满分解 ​

真正的难点在这里 ​

一趟搬移,看一遍 ​

别画蛇添足 ​

下一步 ​