【优选算法系列】第一节.双指针（283. 移动零和1089. 复写零）

作者简介：大家好，我是未央；

博客首页：未央.303

系列专栏：优选算法系列

每日一句：人的一生，可以有所作为的时机只有一次，那就是现在！！！！！

前言

双指针算法介绍

常见的双指针有两种形式，一种是对撞指针，一种是左右指针。

---

对撞指针：一般用于顺序结构中，也称左右指针。

对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。

                                                                                                                                                  

• 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：

◦ left == right （两个指针指向同一个位置）

◦ left > right （两个指针错开）

---

快慢指针：又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。 这种方法对于处理环形链表或数组非常有用。

其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。

                                                                                                                                                  

快慢指针的实现方式有很多种，最常用的一种就是：

• 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。

一、移动零

1.1 题目描述

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

---

注意 ，必须在不复制数组的情况下原地对数组进行操作。

---

提示:

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

示例1：

---

示例2：

1.2 题目解析

1.2.1 算法原理

解题方法：（快排的思想：数组划分区间 - 数组分两块）

                                                                                                                                                  

解题思路：

在本题中，我们可以⽤⼀个 cur 指针来扫描整个数组，另⼀个 dest 指针⽤来记录⾮零数序列的最后⼀个位置。

根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。

                                                                                                                                                  

在 cur 遍历期间，使 [0, dest] 的元素全部都是⾮零元素， [dest + 1, cur - 1] 的

元素全是零。

---

算法步骤流程：

步骤一：

初始化 cur = 0 （⽤来遍历数组）， dest = -1 （指向⾮零元素序列的最后⼀个位置。

因为刚开始我们不知道最后⼀个⾮零元素在什么位置，因此初始化为 -1 ）

---

步骤二：

cur 依次往后遍历每个元素，遍历到的元素会有下⾯两种情况：

                                                                                                                                                  

情况一：

i. 遇到的元素是 0 ， cur 直接 ++ 。因为我们的⽬标是让 [dest + 1, cur - 1] 内 的元素全都是零，因此当 cur 遇到 0 的时候，直接 ++ ，就可以让 0 在 cur - 1 的位置上，从⽽在 [dest + 1, cur - 1] 内；

                                                                                                                                                  

情况二：

ii. 遇到的元素不是 0 ， dest++ ，并且交换 cur 位置和 dest 位置的元素，之后让 cur++ ，扫描下⼀个元素。

---

情况二解析：

因为 dest 指向的位置是⾮零元素区间的最后⼀个位置，如果扫描到⼀个新的⾮零元 素，那么它的位置应该在 dest + 1 的位置上，因此 dest 先⾃增 1 ；

                                                                                                                                                  

dest++ 之后，指向的元素就是 0 元素（因为⾮零元素区间末尾的后⼀个元素就是 0 ），因此可以交换到 cur 所处的位置上，实现 [0, dest] 的元素全部都是⾮零 元素， [dest + 1, cur - 1] 的元素全是零。

1.2.2 代码编写

代码解析：

二、复写零

2.1 题目描述

描述：
给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

---

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

---

提示：

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 9

示例1：

---

示例2：

2.2 题目解析

2.2.1 算法原理

解题方法：解法（原地复写 - 双指针）

算法思路 ：

如果「从前向后」进⾏原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。

但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」，因此我们的⼤体流程分两步：

• i. 先找到最后⼀个复写的数；
• ii. 然后从后向前进⾏复写操作。 

---

解题步骤：

步骤一：  初始化两个指针 cur = 0 ， dest = 0 ；

---

步骤二： 找到最后⼀个复写的数：

i.当 cur < n 的时候，⼀直执⾏下⾯循环：

（1）先判断 cur 位置的元素:

（2）如果是 0 的话， dest 往后移动两位； 否则， dest 往后移动⼀位。

（3）判断 dest 时候已经到结束位置，如果结束就终⽌循环；

（4）如果没有结束， cur++ ，继续判断。

---

步骤三：注意需要处理边界情况（判断 dest 是否越界到 n 的位置）

i.如果越界，执⾏下⾯三步：

（1）n - 1 位置的值修改成 0 ；

（2）cur 向前移动⼀步；

（3）dest 向前移动两步 。

图示说明边界情况：

---

步骤四：从 cur 位置开始从后往前遍历原数组，依次还原出复写后的结果数组。

i. 判断 cur 位置的值：

（1）如果是 0 ： dest 以及 dest - 1 位置修改成 0 ， dest -= 2 ；

（2） 如果⾮零： dest 位置修改成 0 ， dest -= 1 ；

ii. cur-- ，复写下⼀个位置。

2.2.2 代码编写

代码解析：

总结