LeetCode 283 移动零

# 一、题目描述（LeetCode 283.移动零）

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

要求：必须在原数组上操作，不能拷贝额外的数组。

约束条件：

• 1 <= nums.length <= 10^4

• -2^31 <= nums[i] <= 2^31 - 1

示例：

• 输入：nums = [0,1,0,3,12]，输出：[1,3,12,0,0]

• 输入：nums = [0]，输出：[0]

# 二、两种解题思路 & Java代码

# 1. 辅助列表法（新手理解，不推荐面试）

# 思路

遍历数组，将所有非零元素收集到一个新列表中，然后在列表末尾补上相应数量的 0，最后将列表内容写回原数组。

# 复杂度

时间复杂度：O(n)，空间复杂度：O(n)（需要额外列表）

# 代码

class Solution {
    public void moveZeroes(int[] nums) {
        List<Integer> nonZero = new ArrayList<>();
        // 收集所有非零元素
        for (int num : nums) {
            if (num != 0) {
                nonZero.add(num);
            }
        }
        // 写回原数组：先写非零元素，再补零
        for (int i = 0; i < nums.length; i++) {
            if (i < nonZero.size()) {
                nums[i] = nonZero.get(i);
            } else {
                nums[i] = 0;
            }
        }
    }
}

# 问题

• 使用了额外的 O(n) 空间，不满足题目"原地操作"的要求

• 面试中面试官会追问：能否做到 O(1) 空间？

# 2. 双指针交换法（面试最优解）⭐

# 核心思路

使用两个指针：

• i（遍历指针）：从左到右逐个扫描数组元素

• insertPos（插入指针）：始终指向"下一个非零元素应该放的位置"

遍历过程中，只要 i 遇到非零元素，就和 insertPos 位置的元素交换，然后 insertPos 右移一位。这样所有非零元素会按原顺序被"收集"到数组前端，0 自然被挤到末尾。

# 复杂度

时间复杂度：O(n)，空间复杂度：O(1)

# 代码

class Solution {
    public void moveZeroes(int[] nums) {
        // insertPos 记录下一个非零元素应该放的位置
        int insertPos = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                // 交换到前面
                int temp = nums[insertPos];
                nums[insertPos] = nums[i];
                nums[i] = temp;
                insertPos++;
            }
        }
    }
}

# 三、算法执行过程动图演示

以输入 nums = [0, 1, 0, 3, 12] 为例，逐步演示双指针交换法的执行过程：

# 初始状态

数组:  [ 0,  1,  0,  3, 12]
        ↑               ↑
    insertPos=0       i=0

# 第 1 步：i=0，nums[0]=0

遇到 0，跳过不交换，insertPos 不动

数组:  [ 0,  1,  0,  3, 12]
        ↑       ↑
    insertPos=0  i=1（右移）

# 第 2 步：i=1，nums[1]=1 ≠ 0

非零元素！交换 nums[insertPos] 和 nums[i]，然后 insertPos++

交换前:  [ 0,  1,  0,  3, 12]
          ↑   ↑
      insertPos=0  i=1

交换后:  [ 1,  0,  0,  3, 12]
              ↑   ↑
          insertPos=1  i=2（右移）

# 第 3 步：i=2，nums[2]=0

遇到 0，跳过不交换

数组:  [ 1,  0,  0,  3, 12]
              ↑       ↑
          insertPos=1  i=3（右移）

# 第 4 步：i=3，nums[3]=3 ≠ 0

非零元素！交换 nums[insertPos] 和 nums[i]，然后 insertPos++

交换前:  [ 1,  0,  0,  3, 12]
              ↑       ↑
          insertPos=1  i=3

交换后:  [ 1,  3,  0,  0, 12]
                  ↑       ↑
              insertPos=2  i=4（右移）

# 第 5 步：i=4，nums[4]=12 ≠ 0

非零元素！交换 nums[insertPos] 和 nums[i]，然后 insertPos++

交换前:  [ 1,  3,  0,  0, 12]
                  ↑       ↑
              insertPos=2  i=4

交换后:  [ 1,  3, 12,  0,  0]
                      ↑
                  insertPos=3（i 已越界，结束）

# 最终结果

[ 1,  3, 12,  0,  0 ]
 ✅ 非零元素保持原顺序    ✅ 零全部移到末尾

# 四、为什么交换法能保持非零元素顺序？

这是很多初学者的疑问。关键在于 insertPos 永远不会超过 i。

• 当 insertPos == i 时，交换的是自己和自己，相当于什么都没做

• 当 insertPos < i 时，nums[insertPos] 一定是 0（因为之前的非零元素都已经被交换到前面了），所以交换后不会破坏已有顺序

本质：insertPos 就像一条"分割线"，左边全是已排好序的非零元素，右边是待处理的区域。

# 五、关键问题解答

# 1. 为什么不用排序或额外数组？

• 题目要求原地修改，额外数组会占用 O(n) 空间

• 排序虽然能实现，但时间复杂度是 O(n log n)，不如双指针 O(n) 高效

• 双指针法是时间和空间的最优平衡

# 2. insertPos 和 i 之间是什么关系？

• insertPos <= i 始终成立

• insertPos 到 i 之间的元素全部是 0

• 每次交换实际上是把一个非零元素"穿过"这段 0 区域，放到正确位置

# 3. 全是 0 或全不是 0 的数组会怎样？

• 全是 0：nums[i] != 0 永远不成立，insertPos 不动，数组不变

• 全不是 0：每次 insertPos == i，自己和自己交换，数组不变

• 两种极端情况都能正确处理，不会出错

# 六、双指针法核心模板（必背）

# 核心结论

当题目要求"原地修改数组、移动/去重元素、保持顺序"时 → 第一时间想到双指针

# 通用模板

int insertPos = 0;
for (int i = 0; i < nums.length; i++) {
    if (满足条件的元素) {
        nums[insertPos] = nums[i];  // 或交换
        insertPos++;
    }
}

# 三大经典双指针数组题

题目	条件判断	操作
移动零（本题）	nums[i] != 0	交换
移除元素（LeetCode 27）	nums[i] != val	覆盖
删除有序数组重复项（LeetCode 26）	nums[i] != nums[i-1]	覆盖

# 秒杀口诀

原地改，双指针；前面存结果，后面扫全局。

# 七、复杂度分析

解法	时间复杂度	空间复杂度
辅助列表法	O(n)	O(n)
双指针交换法	O(n)	O(1)

• 时间复杂度：只遍历数组一次，每个元素最多被交换一次 → O(n)

• 空间复杂度：只用了两个指针变量，没有额外数据结构 → O(1)