移除元素 | 每日算法 · 变量语义法

📋 题目描述

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

示例 1

输入：nums = [3,2,2,3], val = 3

输出：2, nums = [2,2,_,_]

函数应返回 k = 2，并且 nums 中的前两个元素均为 2。返回的 k 个元素之外留下什么并不重要。

示例 2

输入：nums = [0,1,2,2,3,0,4,2], val = 2

输出：5, nums = [0,1,4,0,3,_,_,_]

函数应返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4（顺序可任意）。

💭 模拟答题者思考

1. 我先想暴力：开一个新数组 res，从左到右扫 nums，遇到不等于 val 的就 append——逻辑对，但用了 O(n) 额外空间，题目要求原地修改。

2. 重复在哪里？每个元素只需判断一次「要不要保留」，保留的元素要紧凑写到数组前部。我不需要真正「删除」，只需把要保留的值覆盖到前面即可。

3. 双指针：用 slow 标记下一个写入位置（也是已保留个数），用 fast 从 0 开始扫描。若 nums[fast] != val，就把它写到 nums[slow] 并 slow++。

4. 为什么可以覆盖？slow 永远 ≤ fast：每遇到一个要移除的元素，slow 不动而 fast 前进，所以写入位置不会越过当前扫描位置，不会覆盖尚未处理的元素。

5. 最终 nums[0..slow-1] 即为保留结果，返回 slow。每个元素访问一次，时间 O(n)，仅用两个下标，空间 O(1)。本题不要求保持原顺序，此写法最直观。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`slow`	int	定义：下一个「保留元素」应写入的下标，也是当前已保留元素个数维护：初始 `slow = 0`；`nums[0..slow-1]` 均为不等于 `val` 的元素更新：当 `nums[fast] != val` 时，执行 `nums[slow] = nums[fast]; slow++`
`fast`	int	定义：扫描指针，从 `0` 到 `n-1` 遍历整个数组维护：每轮检查 `nums[fast]` 是否等于 `val`，等于则跳过（不写），不等于则复制到保留区更新：每轮循环末尾 `fast++`，直到遍历完所有元素
`k`（返回值）	int	定义：数组中不等于 `val` 的元素个数维护：等于循环结束后的 `slow`（每保留一个元素 `slow` 就 +1）更新：循环结束后直接返回 `slow`，无需额外计数器

⌨️ 落码步骤

1. 令 slow = 0，表示保留区下一个写入位置

2. for fast in range(len(nums))：若 nums[fast] != val，则 nums[slow] = nums[fast]，slow += 1

3. 循环结束，nums[0..slow-1] 为所有不等于 val 的元素

4. 返回 slow 作为保留元素个数 k

💻 代码实现

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0  # nums[0..slow-1] 为已保留的元素
        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
        return slow

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;  // nums[0..slow-1] 为已保留的元素
        for (int fast = 0; fast < nums.size(); fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
};
// 时间 O(n)，空间 O(1)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(1)

⚠️ 常见坑

❗ 返回值是 slow 而不是 slow - 1：本题 slow 表示「已保留个数」，与 #26 去重题（slow 是最后下标）语义不同。

❗ 写入顺序错误：应先判断 nums[fast] != val 再写入并 slow++，遇到 val 时 slow 不能动。

❗ 误以为必须保持原顺序：本题允许打乱顺序，从左到右覆盖即可；若强行保持顺序需更复杂的双指针写法，此处不必。

🔍 必测边界 Case

Case 1：空数组

nums = [], val = 1 → 0（循环不执行，直接返回 0）

Case 2：全部为 val

nums = [3,3,3], val = 3 → 0（无元素被保留，slow 始终为 0）

Case 3：无 val

nums = [1,2,3], val = 4 → 3, nums = [1,2,3]（每个元素都被保留，slow 最终为 3）