移动零

怎样从“给定数组 [0,1,0,3,2],原地把所有 0 移到末尾,保持非零元素的相对顺序。”推导出 数组写游标 · 快慢指针，并证明每次状态变化都不会漏掉答案？

中心结论：slow 指向下一个非零应放的位置;fast 扫描,遇到非零就与 slow 交换并前移 slow。

题目要求不能采用额外的辅助空间，将数组中 0 元素都移动到数组的末尾，并且维持所有非 0 元素的相对位置。

在本站主例中，给定数组 [0,1,0,3,2],原地把所有 0 移到末尾,保持非零元素的相对顺序。

算法最终需要得到或观察：数组变为 [1,3,2,0,0],非零在前且保持原序,零在末尾。

为每个位置复制或删除元素，会产生重复搬运；先建立正确基线，再把有效元素原地覆盖到写指针位置。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“读写游标”，明确答案需要观察什么。
2. 2状态只维护 非零写位 slow、扫描指针 fast、已就位非零个数。
3. 3转移每一步按照 slow 指向下一个非零应放的位置;fast 扫描,遇到非零就与 slow 交换并前移 slow。
4. 4收尾读取 数组变为 [1,3,2,0,0],非零在前且保持原序,零在末尾。，并复核边界与复杂度。

读指针负责发现信息，写指针只在答案确定时落笔。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：非零写位 slow、扫描指针 fast、已就位非零个数。

这一题可以只扫描数组一遍，不断的用 i，j 标记 0 和非 0 的元素，然后相互交换，最终到达题目的目的。与这一题相近的题目有第 26 题，第 27 题，第 80 题。

slow 指向下一个非零应放的位置;fast 扫描,遇到非零就与 slow 交换并前移 slow。

执行过程中持续维护：非零写位 slow、扫描指针 fast、已就位非零个数。

正确性依赖以下不变量：下标区间 [0, slow) 是已就位的非零元素,保持相对顺序。；下标区间 [slow, fast) 全为 0。

面试时可以压缩为：我用快慢指针:slow 是非零写位,fast 扫描,遇到非零就和 slow 交换并前移 slow;一趟完成,非零保序、零自然沉底,O(n)/O(1)。

落到当前题，执行机制可以压缩为：slow 指向下一个非零应放的位置;fast 扫描,遇到非零就与 slow 交换并前移 slow。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入给定数组 [0,1,0,3,2],原地把所有 0 移到末尾,保持非零元素的相对顺序。 因为：slow 指向下一个非零应放的位置;fast 扫描,遇到非零就与 slow 交换并前移 slow。
2. 2检查 a[fast]=0读取 a[fast]=0,与判定规则比较。 因为：0 不满足保留条件,应当被留下零。
3. 3检查 a[fast]=1读取 a[fast]=1,与判定规则比较。 因为：1 非零,应当进入结果区。
4. 4前移非零 1把非零值 1 交换到 slow 处,slow 前移。 因为：slow 永远指向「下一个待写入位置」,所以写完必须前移,否则会覆盖结果。
5. 5留下零 00 不进入结果,slow 不动,fast 继续向前。 因为：只有 fast 单独前移,才能让 slow 这个写位「等着」下一个该保留的值。
6. 6前移非零 3把非零值 3 交换到 slow 处,slow 前移。 因为：slow 永远指向「下一个待写入位置」,所以写完必须前移,否则会覆盖结果。
7. 7前移非零 2把非零值 2 交换到 slow 处,slow 前移。 因为：slow 永远指向「下一个待写入位置」,所以写完必须前移,否则会覆盖结果。
8. 8收尾与复杂度数组变为 [1,3,2,0,0],非零在前且保持原序,零在末尾。 因为：时间 O(n) · 空间 O(1)。slow 指向下一个非零应放的位置;fast 扫描,遇到非零就与 slow 交换并前移 slow。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func moveZeroes(nums []int) {
	if len(nums) == 0 {
		return
	}
	j := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] != 0 {
			if i != j {
				nums[i], nums[j] = nums[j], nums[i]
			}
			j++
		}
	}
}

func main() {
    // 1. 主例
    //    输入：mode="move-zeroes", array=[0,1,0,3,2]
    //    期望：数组变为 [1,3,2,0,0],非零在前且保持原序,零在末尾。
    //
    // 2. 失败 / 未命中
    //    检查：用「先覆盖再补零」两趟也行,但交换法一趟完成且天然保序。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC27 移除元素；LC26 有序数组去重
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意给定数组 [0,1,0,3,2],原地把所有 0 移到末尾,保持非零元素的相对顺序。
2. 2重复为每个位置复制或删除元素，会产生重复搬运；先建立正确基线，再把有效元素原地覆盖到写指针位置。
3. 3优化slow 指向下一个非零应放的位置;fast 扫描,遇到非零就与 slow 交换并前移 slow。
4. 4证明下标区间 [0, slow) 是已就位的非零元素,保持相对顺序。；下标区间 [slow, fast) 全为 0。
5. 5复杂度时间 O(n)，空间 O(1)