优选算法系列（1. 双指针_上）
目录
双指针
一：移动零（easy）
题目链接：移动零
解法:
代码：
二：复写零（easy）
题目链接：复写零
编辑
解法：
代码：
三：快乐数（medium）
解法：
拓展（鸽巢原理）：
代码：
四. 盛水最多的容器（medium）
题目链接：盛水最多的容器
解法：
代码：
双指针
- 对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
- 对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
- left == right （两个指针指向同⼀个位置）
- left > right （两个指针错开）
- 在⼀次循环中，每次让慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢。
一：移动零（easy）
题目链接：移动零
解法:
- 两个指针（数组用下标替代）：
cur：从左往右扫描数组，遍历数组
dest：已处理的区间内最后一个非零元素（没有处理过的区间最开始定义为-1）
- 三个区间
[0,dest]: 非0元素
[dest，cur-1]: 0
[cur-1,size-1]: 待处理区间
如何实现：
cur的遍历过程中：
- 遇到0元素：不处理（cur++）
- 遇到非零元素： 交换 dest+1和cur，dest++，cur++
代码：
二：复写零（easy）
题目链接：复写零
解法：
根据“异地”操作，优化为本地操作。
- 异地操作：
通过“异地”复写可以很简单地完成这个题目但是题目要求“本地”操作
- 本地操作
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）
解法：
- 情况⼀：⼀直在 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）
题目链接：盛水最多的容器
解法：
- 解法⼀（暴⼒求解）（会超时）：
- 解法⼆（对撞指针）：
我们先给一个区间取最两边的两个值算出 v1
然后我们以两边较小的值向内取值（2，5，4）我们会发现有两种情况
- h（高度不变）* w（宽度变小）= v（体积减小）
- h（高度变小）* w（宽度变小）= v（体积减小）
因此我们可以将这种单调性质应用上
代码：
