LeetCode 27. 移除元素

约 4 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 5-10 面试经典 150 题 字节 美团
标签
数组 双指针

题目描述

✅ 27. 移除元素

image-20260928235643783

image-20260928235643785

题意分析

在原数组中去掉所有等于 val 的元素，返回剩余数量 k，并把这些保留元素放到前 k 个位置。数组物理长度不需要改变，k 之后的旧值也不属于结果。

因此不必每删除一个元素就搬动整个后缀，只需从左到右筛选，把保留元素依次写入数组前部。

解法：快慢指针覆盖

核心思路

[!blue]

fast 负责读取每个元素，slow 表示已保留的数量，同时也是下一个写入位置。每轮开始时，[0, slow) 恰好按原顺序保存了已扫描部分中所有不等于 val 的元素。

若 nums[fast] == val，不写入，也不移动 slow，有效前缀保持不变；否则将它写到 nums[slow]，再让 slow 加一，恰好把当前保留元素接在已有结果后面。两种情况都维持上述前缀含义。

处理 fast 前，保留数量不会超过已经读过的元素数，因此 slow <= fast。写入只会覆盖已处理的位置，或写回当前位置，不会破坏尚未读取的元素。全部扫描结束后，有效前缀就是最终结果，返回 slow 即可。

解题步骤

  1. 初始化 slow = 0，表示有效前缀当前为空。
  2. 用 fast 从左到右扫描数组。
  3. 若 nums[fast] == val，跳过当前元素；否则将它写到 nums[slow]，并令 slow++。
  4. 扫描完成后返回 slow，无需清理其后的数组位置。

空数组不会进入循环；所有元素都需要删除时，slow 也始终为零。这两种情况都自然返回 0，无需额外分支。

代码实现

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;

        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                // 写入有效前缀；写指针不超过读指针，不会覆盖尚未读取的元素。
                nums[slow] = nums[fast];
                slow++;
            }
        }

        return slow;
    }
}

func removeElement(nums []int, val int) int {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != val {
            // 写入有效前缀；写指针不超过读指针，不会覆盖尚未读取的元素。
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}

复杂度分析

  • 时间复杂度：$O(n)$，每个元素读取一次，非 val 元素至多写入一次。
  • 空间复杂度：$O(1)$，只使用常数个指针变量，结果直接写回原数组。

关键点总结

[!green]

  • 原地删除的本质是构造有效前缀，不是改变数组长度；返回值 k 划定了结果边界。
  • slow 表示已保留元素数，也表示下一个写入位置；一个变量承担两种一致的含义，可避免额外计数。
  • slow <= fast 是安全覆盖的关键：写指针不会越过读指针，尚未读取的数据始终完好。
  • 当前写法保留相对顺序，返回值之后的旧内容不属于结果。

易错点总结

[!yellow]

  • 读到 val 时仍让 slow 前进：有效前缀会留下待删除元素，返回长度也会偏大。
  • 返回 nums.length 而不是 slow：数组物理长度没有改变，只有前 slow 个位置有效。
  • 写入后额外移动 fast：for 循环已经会更新 fast，再次递增会漏读元素。
  • 清空 slow 之后的元素：题目明确不检查尾部，这既增加无效写入，也可能让人误以为整个数组都是结果。

相似题目

题目 难度 关联与区别
283. 移动零 简单 同样把要保留的元素向前压缩，原题还需把尾部补零，本题尾部内容无要求。
26. 删除有序数组中的重复项 简单 同样用读写指针原地压缩，原题删除有序重复项，本题删除指定值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/47236880
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！