[027] 移除元素 (Remove Element)

难度：简单 | 标签：数组、双指针

题目描述

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

要求： 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。

解法一：快慢指针 (Fast-Slow Pointers) —— 推荐 ✅

这是最稳健的解法，同时保留了元素的相对顺序。

• 快指针 (fast)：寻找新数组的元素（即不等于 val 的元素）。
• 慢指针 (slow)：指向新数组更新的位置。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.size(); fast++) {
            // 如果快指针指向的元素不是要删除的目标
            if (nums[fast] != val) {
                // 把它覆盖到慢指针的位置
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
};

• 时间复杂度：

• 空间复杂度：

解法二：对撞指针 / 元素交换 (Two Pointers - Swap)

如果题目允许改变元素顺序，且要删除的元素很少时，这种方法赋值操作更少。

核心思路是：当左边遇到 val 时，直接用数组最右边的元素覆盖它，然后丢弃最右边的元素。

C++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0;
        int right = nums.size(); // 注意这里是 size，不是 size-1

        while (left < right) {
            if (nums[left] == val) {
                // 发现要删除的元素，直接用最后一个有效元素覆盖它
                nums[left] = nums[right - 1];
                // 数组有效长度减 1
                right--;
                // 注意：这里 left 不自增，因为换过来的新元素可能还是 val，需要下一轮继续检查
            } else {
                left++;
            }
        }
        return left;
    }
};

易错点与核心考点

1. 快慢指针的逻辑： 本质是**“覆盖”**而不是“删除”。我们并不真正删除内存，而是把有效的数据往前挪，最后返回有效数据的长度即可。
2. 对撞指针的陷阱：
   • 覆盖方向：一定是用由右边的元素覆盖左边的 val，不能反过来。
   • 循环检查：当把右边的元素换过来后，left 指针不能立即前进，因为换过来的那个数可能也等于 val，必须在下一次循环中再次检查它。
3. 引用传参： 题目参数是 vector<int>& nums，意味着你的修改会直接影响外部的数组。

总结

• 内存使用：两者一样，都是 。

• 运行效率：

  • 如果要删除的元素很少，对撞指针可能更快（因为写操作少）。

  • 如果要删除的元素很多，或者元素分布均匀，两者差不多。