优选算法系列（1. 双指针_上）

目录

双指针

一：移动零（easy）

题目链接：移动零

解法:

代码：

二：复写零（easy）

题目链接：复写零

​编辑

解法：

代码：

三：快乐数（medium）

解法：

拓展（鸽巢原理）：

代码：

四. 盛水最多的容器（medium）

题目链接：盛水最多的容器

解法：

代码：

---

双指针

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

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

• 对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
• 对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：

1. left == right （两个指针指向同⼀个位置）
2. left > right （两个指针错开）

快慢指针： ⼜称为⻳兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。

这种⽅法对于处理环形链表或数组⾮常有⽤。

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

快慢指针的实现⽅式有很多种，最常⽤的⼀种就是：

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

一：移动零（easy）

题目链接：移动零

解法:

⽤⼀个 cur 指针来扫描整个数组，另⼀个 dest 指针⽤来记录⾮零数序列的最后⼀个位置。根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。在 cur 遍历期间，使 [0, dest] 的元素全部都是⾮零元素， [dest + 1, cur - 1] 的

元素全是零。

• 两个指针（数组用下标替代）：

                cur：从左往右扫描数组，遍历数组

                dest：已处理的区间内最后一个非零元素（没有处理过的区间最开始定义为-1）

• 三个区间

                [0,dest]: 非0元素
                [dest，cur-1]: 0

                [cur-1,size-1]: 待处理区间

如何实现：

cur的遍历过程中：

1. 遇到0元素：不处理（cur++）
2. 遇到非零元素： 交换 dest+1和cur，dest++，cur++                

代码：

---

二：复写零（easy）

题目链接：复写零

解法：

根据“异地”操作，优化为本地操作。

• 异地操作：

通过“异地”复写可以很简单地完成这个题目但是题目要求“本地”操作

• 本地操作

如果「从前向后」进⾏原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数「被覆

盖掉」。

                        2会被覆盖掉 

因此我们选择「从后往前」的复写策略。

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

步：

1. 先找到最后⼀个复写的数；（两种方法）
2. 然后从后向前进⾏复写操作

在这里找最后⼀个复写的数提供两种方法

方法1：

让cur和dest都先指向第一个元素

当dest>=size-1的时候cur就是最后一个要复写的数。

特殊情况下：dest=arr.size();

方法2：

由于每有一个0就需要多写一次，这也就意味着每有一个0原数组的最后一位都不会出现在复写之后的数组里面。

据此我们让dest等于最后一个元素cur从前往后遍历，每次遇到一个0就让dest向前移动一位，当cur和dest相遇的位置就是最后要复写的数。

特殊情况下dest<cur. 

特殊情况的处理：

当最后一个要复写的数为0的时候我们如果复写两次就会造成错误，此时我们需要特殊处理让最后的0只写一次

代码：

---

三：快乐数（medium）

题⽬链接：快乐数

解法：

题⽬告诉我们，当我们不断重复 x 操作的时候，计算⼀定会「死循环」，死的⽅式有两种：

• 情况⼀：⼀直在 1 中死循环，即 1 -> 1 -> 1 -> 1......
• 情况⼆：在历史的数据中死循环，但始终变不到 1

由于上述两种情况只会出现⼀种，因此，只要我们能确定循环是在「情况⼀」中进⾏，还是在「情况⼆」中进⾏，就能得到结果。

我们可以将这两种情况抽象一下：

也就是说，快乐数其实我们也可以看作最终会陷入一个循环只不过每次都是1.

这种图形在之前的代换链表相关问题中有提到过

带环链表的快速判断与入环点寻找方法-CSDN博客

在那里我们用快慢指针判断一个链表是否带换，而本题一定会带环，因此我们使用快慢指针的思想那么快乐数的两个指针相遇一定为1，不是快乐数的两个指针相遇则不为1.

当然这里的指针是一种思想并不一定是指针，它也可以是一个数字。

拓展（鸽巢原理）：

这里的题目告诉了我们只有这两种情况，那如果题目不给（情况⼆：在历史的数据中死循环，但始终变不到 1）这一条件，那是否存在一直变下去不为1且不成环的情况呢？

这里我们就需要用到 鸽巢原理（抽屉原理）：意思是有n个鸽子和n+1个巢穴，那么至少有一个巢穴有不止一个鸽子。

我们都知道int的最大值为2^31，结果就是

我们直接让每位都变成9也就是9999999999（10个9）试通过题目 x 操作的那种计算方式下达到最大值（9*9*10=810）这意味着在int范围内无论取什么数通过 x 操作都不可能超过810。那么我们随机取一个数进行至多811次操作就一定会得到重复的数字。即一定会成环！

代码：

 

---

四. 盛水最多的容器（medium）

题目链接：盛水最多的容器

解法：

• 解法⼀（暴⼒求解）（会超时）：

枚举出能构成的所有容器，找出其中容积最⼤的值。

容器容积的计算⽅式：

设两指针 i , j ，分别指向⽔槽板的最左端以及最右端，此时容器的宽度为 j - i 。由于容器的⾼度由两板中的短板决定，因此可得容积公式 ： v = (j - i) * min(height[i], height[j])

• 解法⼆（对撞指针）：

我们先给一个区间取最两边的两个值算出 v1

然后我们以两边较小的值向内取值（2，5，4）我们会发现有两种情况

1. h（高度不变）* w（宽度变小）= v（体积减小）
2. h（高度变小）* w（宽度变小）= v（体积减小）

因此我们可以将这种单调性质应用上

代码：