LC283　移动零¶

简单通过率 63.8%python3核心代码模式双指针样例通过牛客 AC数组双指针

一句话

同向双指针：慢指针指向下一个待填的位置，快指针负责挑出非零元素。

解题思路¶

这题考什么¶

要求原地把所有 0 挪到末尾，且非零元素之间的相对顺序不变。「原地 + 保序」这对约束正好是同向双指针（快慢指针）的标准场景，见双指针与滑动窗口。

slow  已经整理好的前缀 nums[0 .. slow-1] 全是非零元素，且保持原序；
      slow 就是下一个非零元素该落的位置
fast  扫描指针，逐个考察 nums[fast]

fast 每遇到一个非零元素就把它写到 slow 处、slow 前进一格；遇到 0 则什么都不做（相当于把它甩在后面）。一趟扫完后， nums[0 .. slow-1] 是全部非零元素、顺序不变，nums[slow .. n-1] 是残留的旧值，再把这一段统一刷成 0 即可。

这样每个元素最多被读一次、写一次，是「尽量减少操作次数」这个进阶要求想要的答案。另一种常见写法是 fast 与 slow 直接交换，写入次数会多一些（每个非零元素都要写两个位置），但可以省掉末尾补零那一趟。

数据规模与复杂度¶

1 <= n <= 1e4，元素是 32 位有符号整数范围内的任意值。时间 O(n)：两个 for 循环各扫一遍，加起来还是线性。空间 O(1)：只有一个下标变量，没有开新数组——题面明确「必须在不复制数组的情况下原地对数组进行操作」。「新建一个列表装非零元素再补零」虽然也是 O(n)，但违反原地这一条。

坑在哪¶

这道题的返回值是 None，答案留在入参 nums 里。所以一切修改都必须是对 nums 的原地写入（nums[i] = ...）。写成 nums = [...] 只是把本地变量重新绑定到一个新列表，调用方手里的原数组一个字节都没变，判题读回入参会拿到未修改的原始数据，全盘判错。同理，nums.sort()、nums[:] = ... 这类作用在原对象上的操作才有效。
补零这一趟的起点是 slow，不是 0，也不是 slow + 1。循环不变量说的是 nums[0 .. slow-1] 已经排好，所以第一个待清零的下标恰好是 slow；写成 slow + 1 会漏掉一个位置，写成 slow - 1 会抹掉一个已经放好的非零元素。
不能在第一趟里边写非零元素边把 nums[fast] 置零。slow <= fast 恒成立，当 slow == fast 时（前缀里还没出现过 0），先写 nums[slow] 再清 nums[fast] 等于把刚写进去的值又抹成 0。分成两趟就没有这个先后陷阱。
全零或全非零都不需要特判：全非零时 slow 走到 n，补零循环一次不进；全零时 slow 停在 0，补零循环把整段刷成 0（本来就是 0，写回无害）。
严格比对：整理后的数组内容与顺序都是唯一确定的，没有多解。

样例复核¶

nums = [0, 1, 0, 3, 12]，期望 [1, 3, 12, 0, 0]。

第一趟（slow 从 0 起）
    fast=0  值 0   跳过                      nums = [0,1,0,3,12]  slow=0
    fast=1  值 1   nums[0]=1，slow=1         nums = [1,1,0,3,12]
    fast=2  值 0   跳过
    fast=3  值 3   nums[1]=3，slow=2         nums = [1,3,0,3,12]
    fast=4  值 12  nums[2]=12，slow=3        nums = [1,3,12,3,12]
第二趟：把下标 3、4 刷成 0     nums = [1,3,12,0,0]

与期望一致。注意 fast=1 那步 slow=0 < fast=1，写入没有覆盖还没读的数据； slow 永远不超过 fast，所以第一趟绝不会破坏尚未扫描的元素。

参考实现¶

solutions/leetcode/LC283/sol.py
from typing import List, Optional


class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        # 循环不变量：nums[0 .. slow-1] 是已经就位的非零元素，保持原相对顺序；
        # slow 同时也是下一个非零元素该写入的位置
        slow = 0
        # 第一趟：把非零元素依次前移压实。slow <= fast 恒成立，
        # 所以写入 nums[slow] 绝不会覆盖尚未被 fast 读过的数据
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow] = nums[fast]     # 原地写，不能重新绑定 nums
                slow += 1
        # 第二趟：slow 之后全是搬走后残留的旧值，统一刷成 0。
        # 起点正是 slow——不变量保证 nums[0 .. slow-1] 已排好，它是第一个待清位置
        for i in range(slow, len(nums)):
            nums[i] = 0
        # 题面要求原地修改，函数本身不返回任何东西；判题读回的是入参 nums

LC283 移动零¶