移除元素

一、题目（LeetCode 27 · 简单 · Hot100）

给定数组 nums 和值 val，原地移除所有数值等于 val 的元素并返回新长度 k。前 k 个元素为不含 val 的元素，顺序不限。超越 k 的部分忽略。

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]    // 下划线部分内容忽略

二、思路演进

2.1 暴力：每遇到一个 val 就整体前移

扫到 nums[i] == val，把 i+1..n-1 整体前移一格，O(n²)。n = 100 时最坏 10^4 次搬移，简单题也不该这么交。

2.2 最优：快慢指针（覆盖法）

维护"已确认保留区"长度 slow。快指针 fast 扫全数组，遇到 nums[fast] != val 就 nums[slow++] = nums[fast]——保留区只进好元素，val 自然被后续覆盖丢弃。一次遍历，每个元素至多被赋值一次。

与 删除链表的倒数第 N 个结点 的"哑结点 + 双指针"是同一个思想家族。一个指针负责探路，一个指针负责落位。

2.3 对照：对撞指针（交换法）

头尾两个指针向中间收。右端先跳过 val（那些位置的值反正要丢）。左端遇到 val 且右端非 val 时交换、双双向中间走。写法更"炫"但分支多（四种左右组合），且破坏相对顺序（本题允许，别题未必）。适合作为面试的"另一种解法"储备，主答仍推快慢指针——分支少、不变量清晰。

三、复杂度分析

• 快慢指针：时间 O(n) 一趟；空间 O(1) 原地。
• 对撞指针：同样 O(n)/O(1)，但交换次数取决于 val 分布，平均多做无效交换。

四、代码

package org.example;

/**
 * @author MUYI
 * 2026-10-17 重写（原 2023-12 对撞交换版保留思想，见 2.3）
 */
public class LeetCode_27 {

    public static void main(String[] args) {
        System.out.println(removeElement(new int[]{3, 2, 2, 3}, 3));   // 期望 2
        System.out.println(removeElement(new int[]{0, 1, 2, 2, 3, 0, 4, 2}, 2)); // 期望 5
        System.out.println(removeElement(new int[]{2}, 3));            // 期望 1
    }

    public static int removeElement(int[] nums, int val) {
        int slow = 0;                                  // [0, slow) 是已确认保留区
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];             // 好元素落位，保留区扩张
            }
        }
        return slow;
    }

    /** 对撞交换版（对照实现） */
    public static int removeElementBySwap(int[] nums, int val) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            if (nums[right] == val) { right--; continue; }   // 右端丢弃区扩张
            if (nums[left]  == val) {
                nums[left++] = nums[right--];                // 拿右端好值盖掉 val
            } else {
                left++;
            }
        }
        return left;
    }

}

五、坑点

• 返回的是长度不是数组：nums 原地修改、返回 slow，评测只看前 k 位——别返回新数组。
• "顺序可变"是本题的免死金牌：对撞交换法成立全靠它。一旦题目要求稳定顺序（如 删除有序数组中的重复项 的同族题），只剩覆盖法可选。
• 对撞版别忘 nums[right] == val 先行短路：右端先清理，左端交换拿到的才保证是好值，否则会把 val 换进保留区。
• 原生数组无法真正"删除"元素——所谓移除就是逻辑长度收缩，这个心智模型对 Java 面试通用。

六、变形追问

• 变体一（删除有序数组中的重复项，LeetCode 26）：把 != val 的判断换成 fast == 0 || nums[fast] != nums[fast-1]，同一套快慢指针骨架。追问点：为什么比较对象是 nums[fast-1] 而不是 nums[slow-1]。有序性下两者等价，但前者的"首见"语义更普适。
• 变体二（移动零，LeetCode 283）：val = 0 且要求保序——覆盖法天然保序直接用。追问点：能否做到最小写次数（只有 slow != fast 时才赋值的剪枝）。
• 链表版：删除链表的倒数第 N 个结点——数组覆盖法在链表上退化为"prev 指针跳接"，对照记忆。

2026-10 新增（E 轨 · Hot100 重写补全，原 2023 纯代码残稿吸收为对照解法）。