目录

双指针

一：移动零（easy）

题目链接：移动零

解法:

代码：

二：复写零（easy）

题目链接：复写零

​编辑

解法：

代码：

三：快乐数（medium）

解法：

拓展（鸽巢原理）：

代码：

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

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

解法：

代码：

---

双指针

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

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

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

一：移动零（easy）

题目链接：移动零

解法:

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

                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）

题目链接：复写零

解法：

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

• 异地操作：

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

• 本地操作

                        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）

解法：

 

---

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

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

解法：

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