好的，我们这次来详细讲解 LeetCode 第 283 题：移动零（Move Zeroes）。

这道题是数组类问题中非常经典且高频的一道，理解它的多种解法对培养算法思维很有帮助。

1. 题目描述

题目：
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例：

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明：

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

2. 题目分析与初步思路

我们先来理解题目的核心要求：

• 保持非零元素的相对顺序：这意味着我们不能用从两头交换的方法（如快速排序的分区），因为那样会打乱顺序。
• 原地操作：不能使用额外数组，空间复杂度应尽量为 O(1)。
• 最小化操作次数：这提示我们寻找高效的遍历方法。

最直观的暴力解法（不推荐，但有助于理解）：

1. 遍历数组，遇到非零数就把它按顺序放到前面。
2. 最后将剩余位置全部填零。

但这种方法需要多次移动元素，效率不高。我们需要更优的解法。

3. 最优解法思路：双指针（快慢指针）

这是解决本题最经典、最高效的方法。我们使用两个指针 slow 和 fast（或者叫 nonZeroIndex 和 currentIndex），在一次遍历中完成任务。

指针定义：

• slow：指向下一个非零元素应该放置的位置。在 slow 之前的所有元素都是已经处理好的非零数。
• fast：当前遍历的指针，用于寻找非零元素。

算法步骤：

1. 初始化 slow = 0。
2. 遍历数组，fast 从 0 到数组末尾：
   • 如果 nums[fast] != 0：
     • 将 nums[fast] 的值赋给 nums[slow]。
     • slow 向后移动一位。
3. 遍历结束后，从 slow 开始到数组末尾的所有位置，全部设置为 0。

为什么这样可行？

• fast 指针负责探索整个数组，寻找非零元素。
• slow 指针维护了“非零区”的边界，所有非零元素都被紧凑地排列在数组头部。
• 最后，slow 指针之后的位置自然就是需要补零的位置。

4. 详细步骤演示（以示例 [0,1,0,3,12] 为例）

我们一步步模拟这个过程：

初始状态：
nums = [0, 1, 0, 3, 12]
slow = 0, fast = 0

步骤 1：fast = 0

• nums[0] = 0，是非零吗？否。
• 不进行赋值操作，slow 不动。
• 状态：slow = 0, fast = 1

步骤 2：fast = 1

• nums[1] = 1，是非零吗？是。
• 执行 nums[slow] = nums[fast] → nums[0] = 1。
• slow 增加 1 → slow = 1。
• 数组变为：[1, 1, 0, 3, 12]（注意，此时索引1的值被复制到了索引0，但很快会被覆盖或不再重要）
• fast = 2

步骤 3：fast = 2

• nums[2] = 0，是非零吗？否。
• 不操作，slow 不动。
• 状态：slow = 1, fast = 3

步骤 4：fast = 3

• nums[3] = 3，是非零吗？是。
• 执行 nums[slow] = nums[fast] → nums[1] = 3。
• slow 增加 1 → slow = 2。
• 数组变为：[1, 3, 0, 3, 12]
• fast = 4

步骤 5：fast = 4

• nums[4] = 12，是非零吗？是。
• 执行 nums[slow] = nums[fast] → nums[2] = 12。
• slow 增加 1 → slow = 3。
• 数组变为：[1, 3, 12, 3, 12]
• fast = 5（遍历结束）

收尾工作：

• 现在 slow = 3，我们从索引 3 开始到末尾（索引4）填充0。
• nums[3] = 0, nums[4] = 0。
• 最终数组：[1, 3, 12, 0, 0]

5. 代码实现（Python）

def moveZeroes(nums):
    """
    Do not return anything, modify nums in-place instead.
    """
    slow = 0
    # 第一次遍历：将非零元素移动到数组前端
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow] = nums[fast]
            slow += 1
    
    # 第二次遍历：将剩余位置填充为0
    for i in range(slow, len(nums)):
        nums[i] = 0

复杂度分析：

• 时间复杂度：O(n)，我们遍历了数组两次，但每个元素只被处理常数次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

6. 优化：一次遍历完成交换

上面的方法需要两次遍历。我们可以优化为一次遍历吗？可以，使用交换代替赋值。

思路：

• 当 fast 遇到非零元素时，与 slow 指向的元素交换。
• 这样，slow 左边都是非零数，且保持了顺序；slow 和 fast 之间是零。

优化后的代码：

def moveZeroes_optimized(nums):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            # 交换 nums[slow] 和 nums[fast]
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

为什么交换可行？

• 当 fast 找到非零数时，如果 slow 和 fast 不同，说明 slow 指向的是一个零（或者是已经被处理过的位置）。
• 交换操作将这个非零数挪到前面，将零（或无用值）换到后面。
• 这样就避免了一次整体补零的操作。

示例 [0,1,0,3,12] 的交换过程简示：

• fast=0: 0，不交换，slow=0
• fast=1: 1≠0，交换(nums[0], nums[1]) → [1,0,0,3,12], slow=1
• fast=2: 0，不交换
• fast=3: 3≠0，交换(nums[1], nums[3]) → [1,3,0,0,12], slow=2
• fast=4: 12≠0，交换(nums[2], nums[4]) → [1,3,12,0,0], slow=3

7. 总结与要点回顾

• 核心思想：使用双指针（快慢指针）区分已处理区域和待处理区域。
• 关键点：
  • slow 指针维护"非零边界"。
  • fast 指针探索数组，寻找非零元素。
• 两种实现：
  • 两次遍历：先紧凑非零元素，再补零。逻辑清晰。
  • 一次遍历交换：边找边交换，效率稍高（减少总操作次数）。
• 适用场景：这种"原地重新排列数组并保持某些元素顺序"的问题，双指针是通用解法。

这道题虽然简单，但体现了算法中分区和双指针的重要思想，是很多更复杂问题的基础。希望这个循序渐进的讲解能让你彻底理解！