移除元素（LeetCode 27）

题目来源：LeetCode 27 · 移除元素

题目

给定数组 nums 和值 val，原地移除所有等于 val 的元素，返回新长度。

注意：本题不要求保持元素顺序——只要前 k 个元素不含 val 即可（k 是新长度）。这正是首尾指针方案可行的前提。

思路：首尾覆盖法

两个指针从两端向中间收缩：

1. left 从左扫描：当前位置不是 val → 位置安全，left 前进
2. 当前位置是 val → 用右端元素覆盖它，right 收缩
3. 右端元素也是 val → 覆盖是「val 赋 val」的无变化赋值，效果等同直接收缩
4. left > right 时结束，left 就是新长度

left 只在当前位置安全时才前进——覆盖来的值下一轮会被重新检查，直到安全才放行。所以前段永不含 val。

动画演示

代码

def removeElement(self, nums: List[int], val: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        if nums[left] == val:
            nums[left] = nums[right]
            right -= 1
        else:
            left += 1
    return left

复杂度

• 时间：O(n)，每轮 left 或 right 至少移动一位，总共 n 次
• 空间：O(1)，原地操作

边界情况

• 空数组：循环不进入，直接返回 0
• 单元素：是 val 返回 0，不是返回 1
• 双元素全 val：右侧跳过 + 覆盖收缩，最终返回 0
• while left <= right 必须带等号：left == right 时还剩最后一个元素，必须再检查一次，否则漏判