[L1] 原地移除数组中的指定元素（快慢指针）

一句话结论

慢指针标记写入位置，快指针扫描过滤，原地覆盖完成移除，时间 O(n)、空间 O(1)。

体系讲解

问题定义

给定数组 $nums 和目标值 $val，原地删除所有等于 $val 的元素，返回剩余元素个数 $k，且 $nums 前 $k 个位置存放有效元素。不允许使用额外数组。

暴力方案的缺陷

每次发现目标值就向前移动后续所有元素——最坏 O(n²)，且需要大量无效拷贝。

快慢指针方案

fast 扫描每个元素，slow 指向下一个待写入位置。
规则：nums[fast] !== val → 写入 nums[slow]，slow++

原始数组: [3, 2, 2, 3]，val = 3
初始:  slow=0, fast=0

fast=0: nums[0]=3 == val, 跳过, fast++
fast=1: nums[1]=2 != val, nums[slow=0]=2, slow=1, fast++
fast=2: nums[2]=2 != val, nums[slow=1]=2, slow=2, fast++
fast=3: nums[3]=3 == val, 跳过, fast++
结果: nums[0..1] = [2, 2], 返回 k=2

去重变体：有序数组移除重复元素，改为 nums[fast] !== nums[slow-1] 时才写入。

变体	判断条件	适用场景
移除指定值	$nums[$fast] !== $val	无序/有序均可
移除有序重复（保留 1 个）	$nums[$fast] !== $nums[$slow - 1]	数组已排序
移除有序重复（保留 2 个）	$nums[$fast] !== $nums[$slow - 2]	数组已排序

考察意图

考查候选人对"原地操作"的理解——能否在不借助额外数组的前提下完成过滤，并正确处理慢指针边界。区分"用 array_filter 一行搞定"与"理解底层覆盖逻辑"的候选人。

追问链

1. 为什么慢指针不用回退？
   简答：慢指针始终指向"已确认有效区域的下一个空位"。快指针每次只写入非目标值，写入后 slow 推进；目标值直接跳过，slow 不动。整个过程单向推进，无需回退。

2. 这道题的时间复杂度是 O(n) 吗？最坏情况是什么？
   简答：是 O(n)。fast 从头到尾走一遍，每个元素恰好被访问一次；slow 移动次数 ≤ fast。最坏情况是没有任何元素等于 val（slow 和 fast 同步前进，但仍是 O(n)）。

3. PHP 中 array_filter() 能替代快慢指针吗？复杂度如何？
   简答：array_filter() 逻辑上等价，但会创建新数组（O(n) 额外空间），且返回的键值不连续（需 array_values() 重建索引，又一次 O(n)）。面试要求"原地 O(1) 空间"时不可用；工程中若不限制空间，可读性更好的 array_filter() 更合适。

4. 有序数组"保留 2 个重复"的去重为何判断 nums[fast] !== nums[slow-2]？
   简答：已写入区域 [0, slow) 的最后 2 个元素由 slow-2 和 slow-1 标记。若 fast 当前值与 slow-2 处相同，说明这个值已经出现了 ≥2 次，再写入就超限；若不同，最多出现 2 次，可以写入。

易错点

1. 慢指针初始值写成 -1：$slow = -1 再做 $nums[++$slow] 的写法虽然等价，但容易和"找第 k 个位置"的语义混淆。统一用 $slow = 0 表示"下一个写入位置"更直观。
2. 去重变体忘记边界判断：$nums[$fast] !== $nums[$slow - 1] 当 $slow === 0 时 $slow - 1 = -1，PHP 中访问负索引不会报错但值为 null，可能导致第一个元素被错误跳过。应在循环前将第一个元素直接写入，或加 $slow === 0 的特判。
3. 忘记返回 $slow 而是返回 count($nums)：原地操作只是覆盖，数组长度不变；有效元素个数是 $slow，直接用 count() 会返回原始长度，是错误的。

代码示例

<?php

// ── 变体 1：移除等于 val 的所有元素 ───────────────────────────────
function removeElement(array &$nums, int $val): int
{
    $slow = 0;
    foreach ($nums as $fast => $v) {
        if ($v !== $val) {
            $nums[$slow++] = $v;
        }
    }
    return $slow; // 前 $slow 个元素为有效结果
}

// ── 变体 2：有序数组去重，每个值最多保留 1 个 ─────────────────────
function removeDuplicates(array &$nums): int
{
    if (empty($nums)) return 0;

    $slow = 1; // nums[0] 直接保留
    for ($fast = 1; $fast < count($nums); $fast++) {
        if ($nums[$fast] !== $nums[$slow - 1]) {
            $nums[$slow++] = $nums[$fast];
        }
    }
    return $slow;
}

// ── 演示 ──────────────────────────────────────────────────────────
$a = [3, 2, 2, 3];
$k = removeElement($a, 3);
var_dump(array_slice($a, 0, $k)); // [2, 2]

$b = [1, 1, 2, 3, 3];
$k = removeDuplicates($b);
var_dump(array_slice($b, 0, $k)); // [1, 2, 3]