DAY23: LeetCode 27 → 283：从移除元素到移动零，理解快慢指针的两种思路

LeetCode 27 → 283：从移除元素到移动零，理解快慢指针的两种思路

目录

• LeetCode 27 → 283：从移除元素到移动零，理解快慢指针的两种思路
• 一、先从 LC 27「移除元素」开始
• • 1、我应该怎么把需要保留的元素放到前面？
  • 2、把这个思路转换成代码
• 二、接下来做 LC 283「移动零」
• 三、我的第一反应：能不能直接交换？
• • 1、两个指针应该怎么移动？
  • 2、问题可能出在指针的职责上
• 四、方法一：沿用 LC 27，先整理非零元素，再补零
• • 方法一的完整代码
  • • 1. 为什么补零的 while 要放在 for 外面？
    • 2. 为什么覆盖写入不会破坏还没扫描的元素？
• 五、重新回到最开始的想法：交换法能不能实现？
• • 为什么交换法中的 i 一定可以安全交换？
  • 为什么交换法不会打乱非零元素的顺序？
  • 方法二：交换法的完整代码
• 六、两种方法有什么区别？
• 七、从 LC 27 到 LC 283，可以学到什么？

一、先从 LC 27「移除元素」开始

LeetCode 27：移除元素

这道题的要求是：给定一个数组 nums 和一个值 val，把数组中所有等于 val 的元素移除，并返回剩余元素的数量。

注意，题目要求原地修改数组，不能另外创建一个数组来保存结果。

例如：

nums = [3, 2, 2, 3]
val = 3

我们希望最后保留下来的是：

[2, 2]

返回：

2

但这里有一个容易忽略的地方：题目并不要求真的把原数组缩短，只需要保证前两个位置是正确的保留元素。

所以即使最后数组是：

[2, 2, 2, 3]

也没有问题，因为返回值是 2，题目只检查前两个元素。

1、我应该怎么把需要保留的元素放到前面？

很直接：从左到右扫描数组，遇到 val 就跳过，遇到其他数字就保留下来。

但这里又有一个问题：

我知道哪些元素需要保留，可是应该把它们放在哪里？

例如：

[3, 2, 2, 3]

扫描到第一个 2 时，前面的 3 不需要保留，所以这个 2 应该放到下标 0。

扫描到第二个 2 时，它应该放到下标 1。

也就是说，我需要同时知道两件事：

• 当前正在检查哪个元素？
• 下一个保留元素应该写到哪里？

这时候就可以使用两个指针。

j → 负责读取，扫描当前元素
i → 负责写入，记录下一个保留元素的位置

初始时：

i = 0
j = 0

j 每次向后扫描一个元素，如果发现这个元素不等于 val，就把它放到 i 的位置，然后让 i 前进。

例如：

nums = [3, 2, 2, 3]
val = 3

整个过程：

j = 0，遇到 3
→ 不保留，跳过

j = 1，遇到 2
→ 放到 nums[0]
→ i = 1

j = 2，遇到 2
→ 放到 nums[1]
→ i = 2

j = 3，遇到 3
→ 不保留，跳过

最后 i = 2，正好代表已经保留了两个元素。

所以这道题的关键不是去删除某个元素，而是：

让需要保留的元素依次覆盖到数组前面。

2、把这个思路转换成代码

既然 j 只负责从头到尾扫描一次，那么可以直接使用 for。

每当发现一个需要保留的元素，就把它写到 i 的位置，并让 i 加一。

class Solution:
def removeElement(self, nums: list[int], val: int) –> int:
i = 0

for j in range(len(nums)):
if nums[j] != val:
nums[i] = nums[j]
i += 1

return i

这里 i 最后既表示保留元素的数量，也表示下一个可以写入的位置。

这就是 LC 27 的基本思路。

二、接下来做 LC 283「移动零」

LeetCode 283：移动零

这道题要求把数组中的所有 0 移到末尾，同时保持非零元素的相对顺序，并且同样需要原地修改数组。

例如：

nums = [0, 1, 0, 3, 12]

最后应该得到：

[1, 3, 12, 0, 0]

看到这里，可以发现它和 LC 27 有些相似：

LC 27：把不等于 val 的元素保留在前面

LC 283：把不等于 0 的元素保留在前面

但是两道题还有一个明显区别。

LC 27 只要求前面保留的元素正确，后面的内容可以不管。

LC 283 则要求：

非零元素全部放在前面
+
剩余位置全部是零

所以还需要多考虑一步：那些被跳过的零，最后应该怎么处理？

三、我的第一反应：能不能直接交换？

最开始，我想的是：

既然题目要求把零移到后面，那能不能先找到一个零，再去后面寻找非零元素，把它们交换？

例如：

nums = [0, 1, 0, 3, 12]
↑ ↑
i j

我准备让：

i → 寻找前面需要移动的零
j → 寻找后面可以交换的非零元素

当：

nums[i] = 0
nums[j] = 1

就把它们交换：

[1, 0, 0, 3, 12]

这样看起来就能慢慢把非零元素移到前面。

按照这个想法，我最开始写了这个代码（献丑了哈哈哈：

class Solution:
def moveZeroes(self, nums: list[int]) –> None:
i = 0
j = 1

while i < len(nums):
if nums[i] == 0 and nums[j] != 0:
current = nums[j]
nums[j] = 0
nums[i] = current
elif nums[i] == 0 and nums[j] == 0:
j += 1
else:
i += 1

结果不出所料，报错了哈哈哈，主要是漏掉了以下的几个问题。

1、两个指针应该怎么移动？

原本的设想是：

i 找零
j 找非零

但这样一来就需要考虑：

i 找到零以后，要不要停下？

j 找到非零以后，交换完应该怎么移动？

如果连续遇到几个非零元素怎么办？

如果后面已经没有非零元素了怎么办？

很复杂…

例如：

nums = [1, 2, 0, 3]

由于前两个元素都不是零，i 会一直前进，但 j 没有同步前进。

于是可能出现：

i = 2
j = 1

此时 j 已经跑到 i 前面去了，和原本“从零的后面寻找非零元素”的设想不一致。

另外，我的循环条件只判断：

while i < len(nums):

却没有检查 j 是否越界。

如果数组是：

[0, 0, 0]

j 就可能一直增加，最终访问到不存在的下标。

所以这套思路虽然可以继续修补，但指针之间的关系还没有整理清楚。

2、问题可能出在指针的职责上

我发现自己最开始给两个指针安排的是两种不同的寻找任务：

i → 寻找零
j → 寻找非零

这样就需要分别控制两个指针什么时候停、什么时候走。

但回头看 LC 27，其实可以换一个更简单的角度：

我真的需要主动寻找零吗？还是只需要把非零元素全部整理到前面？

这就引出了第一种解决方法。

四、方法一：沿用 LC 27，先整理非零元素，再补零

既然 LC 27 已经能把需要保留的元素放到前面，那么 LC 283 也可以先做同样的事情。

重新定义：

j → 负责扫描整个数组
i → 下一个非零元素应该写入的位置

这样 j 不需要寻找特定元素，只需要正常从左到右扫描。

遇到零就跳过，遇到非零元素就写到 i 的位置。

例如：

nums = [0, 1, 0, 3, 12]

过程如下：

j = 0，遇到 0
→ 跳过

j = 1，遇到 1
→ 写入 nums[0]
→ i = 1

j = 2，遇到 0
→ 跳过

j = 3，遇到 3
→ 写入 nums[1]
→ i = 2

j = 4，遇到 12
→ 写入 nums[2]
→ i = 3

此时数组变成：

[1, 3, 12, 3, 12]
↑
i = 3

虽然整个数组还没有完全正确，但前面已经整理好了：

[1, 3, 12, ?, ?]

而 i = 3 表示已经找到了三个非零元素。

那么后面应该怎么办？

既然所有非零元素都已经整理到前面了，剩下的位置自然全部应该是零。

所以我们只需要从 i 开始，把剩余位置填成零：

[1, 3, 12, 0, 0]

这样就得到了第一种方法：

先把所有非零元素依次放到前面，再把剩余位置全部填成零。

方法一的完整代码

现在思路已经明确：

先扫描
→ 把非零元素放到前面

再补零
→ 把剩余位置全部改成零

对应代码：

class Solution:
def moveZeroes(self, nums: list[int]) –> None:
i = 0

for j in range(len(nums)):
if nums[j] != 0:
nums[i] = nums[j]
i += 1

while i < len(nums):
nums[i] = 0
i += 1

这里和 LC 27 最大的区别就是最后的 while。

LC 27 只需要保证前 i 个元素正确，所以可以直接返回 i。

但 LC 283 要求整个数组正确，因此还需要把剩余位置全部补成零。

1. 为什么补零的 while 要放在 for 外面？

这里我一开始其实理解错了。

我原本以为需要一边把非零元素往前放，一边把后面的位置补成零，但后来重新想了一遍，才发现其实它们可以是两个独立的步骤。

第一步：先把所有非零元素整理到前面。

例如：

nums = [0, 2, 0, 3]

通过 for 循环，让 j 扫描整个数组，遇到非零元素就写到 i 的位置。

扫描结束后：

[2, 3, 0, 3]
↑
i = 2

此时前面两个非零元素已经整理好了。至于后面还有什么旧数据，暂时不用管。

第二步：再把剩余位置全部补成零。

因为 for 已经扫描完整个数组，所以我们可以确定：所有需要保留的非零元素都已经放到了前面。

剩下的部分直接从 i 开始填零就可以了：

[2, 3, 0, 3]
↑
i

补零后： [2, 3, 0, 0]

所以，代码并不是同时完成两件事，而是这样设定的：

for 循环
→ 先整理非零元素
→ i 停在下一个需要填充的位置

while 循环
→ 从 i 开始
→ 把剩余位置全部补成零

如果在 for 还没结束时，就把 i 后面的所有位置清零，反而可能覆盖掉尚未扫描的非零元素。

所以，与其想着怎么一边移动一边补零，不如直接把问题拆开：先处理需要保留的元素，再清理剩余的位置。

这样不仅更容易理解，也不需要考虑补零操作会不会影响后面还没扫描到的元素。

2. 为什么覆盖写入不会破坏还没扫描的元素？

还有一个值得注意的问题：

nums[i] = nums[j]

会修改原数组。

那么有没有可能提前覆盖后面还没有读取的元素？

想通这个的·关键在于：

在每轮扫描开始时，i 一定不会超过 j。

因为：

j → 每一轮都向前移动
i → 只有遇到非零元素才向前移动

所以始终满足：

i <= j

例如：

nums = [0, 2, 0, 3]

扫描到 2 时：

i = 0
j = 1

执行：

nums[0] = nums[1]

得到：

[2, 2, 0, 3]

虽然下标 0 的值改变了，但 j 已经来到下标 1，后面还没有读取的元素并没有受到影响。

之后扫描到 3 时：

i = 1
j = 3

执行：

nums[1] = nums[3]

得到：

[2, 3, 0, 3]

所以：

i == j → 把元素写回原来的位置

i < j → 把元素写到前面已经扫描过的位置

不会覆盖 j 后面尚未读取的数据。

这也是覆盖写入法能够成立的原因。

五、重新回到最开始的想法：交换法能不能实现？

虽然覆盖写入法已经解决了问题，但我最开始想到的其实是交换。

所以还可以继续思考：

既然我最终需要把零放到后面，那能不能在整理非零元素的时候，就顺便把零交换到后面？

这里不需要重新回到最开始那种方式：

i 专门找零
j 专门找非零

我们可以保留刚才已经验证过的指针定义：

j → 从左到右扫描
i → 下一个非零元素应该放的位置

区别只在于：

🔖 覆盖写入法：

发现非零元素
↓
直接覆盖 nums[i]

🔖 交换法：

发现非零元素
↓
把 nums[j] 和 nums[i] 交换

这样就有可能在放置非零元素的同时，把原来的零换到后面。

但是这里我又有一个疑惑：

怎么能确定 i 指向的位置就是零？如果 i 指向的是其他非零元素，交换以后会不会打乱原来的顺序？

为什么交换法中的 i 一定可以安全交换？

其实在仔细想之后，可以发现关键就在于两个指针的移动方式不同。

j → 不管遇到什么元素，都会继续往前扫描
i → 只有 j 遇到非零元素时，才会往前移动

也就是说，j 会一直往前走，但 i 不一定会跟着走。

例如：

nums = [2, 0, 0, 3, 1]

最开始：

[2, 0, 0, 3, 1]
↑
i,j

因为第一个元素 2 不是零，所以交换的是它自己，数组不会发生变化。然后 i 和 j 都会继续往前移动。

但当 j 遇到零时，情况就不一样了：

[2, 0, 0, 3, 1]
↑
i,j

此时 j 发现的是零，不满足交换条件，所以 i 不会移动，而 j 仍然继续往前扫描。

[2, 0, 0, 3, 1]
↑ ↑
i j

如果 j 又遇到了零，i 还是不动。

直到 j 找到了下一个非零元素：

[2, 0, 0, 3, 1]
↑ ↑
i j

这时候 i 还停在之前那个零的位置，而 j 已经找到了 3。

于是交换：

[2, 3, 0, 0, 1]

交换完以后，i 才会往前移动，准备放置下一个非零元素。

所以整个过程其实是：

j 遇到非零元素
→ 和 i 交换
→ i 往前走

j 遇到零
→ 不交换
→ i 停在原地
→ j 继续往前找

这样一来，只要前面出现了零，i 就会停下来，而 j 继续往前寻找非零元素。等找到以后，再把它交换到 i 的位置。

如果前面一直没有零，i 和 j 就会同步移动，交换的只是元素自己，也不会影响数组。

所以 i 并不是主动寻找零，而是因为遇到零时不会移动，才自然停在了需要填充的位置上。

这也解释了为什么交换法不需要最后再补零：每次把非零元素换到前面时，原来位置上的零就已经被交换到后面了。

而且 j 始终从左到右扫描，找到的非零元素也会依次放到 i 的位置，因此不会打乱它们原来的相对顺序。

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

题目还有一个要求：

非零元素的相对顺序不能改变。

例如：

nums = [0, 2, 0, 3, 1]

非零元素原来的顺序是：

2 → 3 → 1

而 j 从左到右扫描，找到非零元素的顺序也一定是：

2 → 3 → 1

每找到一个，就依次放到 i 的位置：

初始： [0, 2, 0, 3, 1]

找到 2： [2, 0, 0, 3, 1]

找到 3： [2, 3, 0, 0, 1]

找到 1： [2, 3, 1, 0, 0]

因为 j 不会跳过前面的非零元素去处理后面的，而 i 也始终依次向右移动，所以非零元素的相对顺序不会改变。

方法二：交换法的完整代码

思路明确以后，代码就很简单了。

我们需要做的事情只有：

j 扫描整个数组
↓
遇到零就跳过
↓
遇到非零元素
→ 和 i 交换
→ i += 1

对应代码：

class Solution:
def moveZeroes(self, nums: list[int]) –> None:
i = 0

for j in range(len(nums)):
if nums[j] != 0:
nums[i], nums[j] = nums[j], nums[i]
i += 1

这里：

nums[i], nums[j] = nums[j], nums[i]

是 Python 的交换写法。

相当于：

temp = nums[i]
nums[i] = nums[j]
nums[j] = temp

因为交换时零已经被移到了后面，所以不需要再额外补零。

六、两种方法有什么区别？

两种方法的时间复杂度都是：

O(n)

因为都只需要从左到右扫描数组。

额外空间复杂度都是：

O(1)

因为只使用了几个变量，没有额外创建一个新数组。

交换法代码更短，但并不意味着运行速度一定更快。覆盖写入法和交换法在实际执行时的写入次数可能不同。

七、从 LC 27 到 LC 283，可以学到什么？

现在再去回头看这两道题，我觉得最重要的应该是理解快慢指针为什么能成立。

LC 27 让我先学会：

j → 负责读取
i → 负责写入

通过两个指针，把需要保留的元素依次放到前面。

而 LC 283 在这个基础上多了一个要求：

不仅要把非零元素放到前面
还要把零全部放到后面

所以可以推导出两种方法：

方法一：覆盖写入

先整理非零元素
↓
再把剩余位置补零

方法二：交换

每发现一个非零元素
↓
就把它交换到前面
↓
零自然被换到后面

这两种方法虽然操作不同，但背后的指针定义其实完全一样：

i → 下一个非零元素应该放的位置
j → 当前正在检查的位置

尤其是交换法，让我进一步理解了一个很重要的规律：

i <= j → 不会提前处理尚未扫描的元素

i == j → 交换时只是自己和自己交换

i < j → i 指向的位置一定是已扫描过的零

所以以后再遇到快慢指针题目，应该先问自己：

第一个指针负责什么？第二个指针负责什么？在整个扫描过程中，哪些位置已经处理好了？

只有把这些问题想清楚，才能知道指针什么时候移动、为什么这样移动，以及为什么不会破坏原来的数据。