移动零 图解题解

这道题真正在问什么

原地把数组里所有 0 挪到末尾，同时保持非零元素的相对顺序不变。比如 [0,1,0,3,12] 要变成 [1,3,12,0,0]。两个约束缺一不可：不能复制数组（必须原地）、非零的先后次序不能乱。这直接排除了「新开数组先拷非零再补零」的写法——它顺序对，但不是原地，还白花 O(n) 额外空间。

为什么想到快慢指针

观察目标形态：结果数组就是「前段按原序排好的非零区 + 后段全零区」。既然如此，只需要两个角色分工：快指针 fast 负责从左到右找非零，慢指针 slow 负责记住「非零区右侧的第一个空位」。fast 扫到非零就把它和 slow 位置交换，slow 前进一格；fast 扫到 0 什么都不做。0 不需要被主动搬运——非零元素一个个被换到前面时，0 自然被换去了后面。

算法全程保持的不变量是什么

循环过程中有两条性质始终成立：slow 左边的区域全是非零且保持原始相对顺序；slow 到 fast 之间（若非空）全是 0。理解了这两条就能看懂交换那一步为什么对：fast 遇到非零时，slow 位置上要么是 0（两指针已经错开），要么就是 fast 自己（前面还没出现过 0）。前者把非零换进空位、把 0 甩到后面；后者是原地自换、无副作用。两种情况都让不变量延续到下一轮，扫完全数组时不变量就是最终答案的形态。

为什么交换法不会打乱非零的顺序

fast 从左到右按序发现非零元素，slow 接收它们的位置也从左到右递增：第一个被发现的非零落在最前面，第二个落在第二格，依此类推。非零进入前段的次序就是它们在原数组中的次序，相对顺序自然保持。这也是它优于「遇到 0 再往后找一个非零来填」的原因——那种写法内层还要再扫一遍找非零，最坏退化成 O(n²)，而快慢指针让每个元素只被 fast 看一次。

复杂度与边界情况

时间 O(n)：fast 扫一遍数组，slow 至多也走一遍，每步只做常数次比较和交换。空间 O(1)：只用两个下标变量。极端输入都能自然兜住：全非零时每次交换都是自换，数组不变；全零时 slow 一直停在 0、从不交换。唯一要盯住的实现细节是 slow 只在放下一个非零之后才前进，遇到 0 时绝不能动——slow 一旦跟着 0 走，「指向下一个空位」的含义就被破坏，后面的交换会放错位置。

Python

def moveZeroes(nums):
    slow = 0                       # 下一个非零该放的位置
    for fast in range(len(nums)):  # 快指针扫全数组
        if nums[fast] != 0:        # 找到非零
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1              # 慢指针前进
    # 原地完成, 无返回值

C++

void moveZeroes(vector<int>& nums){
    int slow = 0;                      // 下一个非零该放的位置
    for(int fast = 0; fast < nums.size(); fast++){
        if(nums[fast] != 0){           // 找到非零
            swap(nums[slow], nums[fast]);
            slow++;                    // 慢指针前进
        }
    }
}

Java

public void moveZeroes(int[] nums) {
    int slow = 0;                       // 下一个非零该放的位置
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {          // 找到非零
            int t = nums[slow];         // 交换 slow 与 fast
            nums[slow] = nums[fast];
            nums[fast] = t;
            slow++;                     // 慢指针前进
        }
    }
}