双指针

双指针是非常经典的算法，包括但不限于前后双指针，快慢双指针，特殊双指针。
尤其需要注意的是双指针并不能只局限于指针，数组下标，过程数据都可以成为“指针”。重要的是能够灵活使用双指针的思想，把解题思路捋顺。
下面，我们来会会几道双指针的题目：

283.移动零

家人们 ！！！ 上连接：283.移动零

通过题目，发现这并不是一到很复杂的题。主要难点在于不改变数组的相对顺序。
这里我们使用前后双指针，逐渐遍历完成操作：

1. 首先定义两个数组下标 i j
2. 我们赋予他们不同含义：
   [ 0 ，i）是已经处理过，已经没有零的部分 并按相对顺序排好
   [i , j] 是零的部分
   (j , n) 待处理的部分
3. 我们控制 j 来进行整个数组的遍历，0 到 i是非零数据。
4. 遇到 0 ，i j 位置互换即可
   
   来看代码：（类似冒泡排序的过程，把零向后挪动）

class Solution {
public:void moveZeroes(vector<int>& nums) {for(int i = 0,j = 0;j<nums.size();j++)if(nums[j] != 0) swap(nums[j],nums[i++]);}
};

非常简洁的代码。就可以完成我们的操作。来看效果：

很好！过啦！！！！

1089. 复写零

家人们！！！跟上节奏：1089. 复写零

这道题与前面的移动零很像，但使用的算法细节不同。
这里需要的也是双指针 i j：

1. 首先定义两个数组下标 i j
2. 赋予他们不同含义：
   0 到 i 是处理完的部分
   i 到 j 是 未处理部分
3. 首先使用 i 遍历整个数组，j 负责调换未处理的数据（将数据后移，空出新的零的位置）
   
   来看代码：

class Solution {
public:void duplicateZeros(vector<int>& arr) {for(int i = 0;i<arr.size();i++){if(arr[i] == 0){for(int j = arr.size() - 1 ; j > i ; j--){arr[j] = arr[j - 1];}++i;}}}
};

运行效果：

202. 快乐数

家人们！！！ 继续干：202. 快乐数

这道题是比较特殊的一道题，我们来看奥：
首先看测试用例的 1 9 和 2 ；

可以发现最后都会处于循环：这里可以证明一下为什么都会处于循环：
假设我们最大数为 99999 99999 那对应的数为 810 ，相当于 0 到 9999999999 只有 810 个数与之对应，所以必然会出现循环。
到这里，大家应该也看出这和判断链表是否有环很像，使用快慢指针，慢指针依次进行一步操作，快指针一次两步操作。这里“指针”代指数字。

class Solution {
public://操作函数int getsum(int n ){int sum = 0;while(n){int i = n % 10;sum += i*i;n /= 10;}return sum;}bool isHappy(int n) {//初始化int slow = n;int fast = getsum(n);//进行循环 直到相遇while(slow != fast){slow = getsum(slow);fast = getsum(getsum(fast));}//判断一下即可if(slow == 1) return true;return false;}
};

来看效果：

很好！ 过啦！！！！

11. 盛最多水的容器

家人们，终于到了最后一题： 11. 盛最多水的容器
这道题可谓十分抽象：

这里使用前后双指针，代我细细到来为什么：
首先我们选取前后这一片段，然后得到一个体积值。
这时我们可以进行一下分析：

1. 如果移动较大这边的指针，那长必然减小 ， 高一定不会增加所以不需移动较高这边
2. 再来看较小这边，移动后不能确定到底是增加还是减少，所以需要移动进行遍历

根据这两条规矩我们就可以完成操作：来看图解（来自 力扣官方题解）

这样必然可以得到答案。

class Solution {
public:int maxArea(vector<int>& height) {int i = 0;int j = height.size() - 1;// 记录答案值int ans = 0;while(i != j){//求得新的体积int v = min(height[i],height[j]) * (j - i);//取最大值ans = max(ans,v);// 移动较小的指针if(height[i] < height[j])i++;elsej--;}return ans;}
};

来看效果：

过啦！！！（还存在改进空间）

经过这四道题目的洗礼，我大概对双指针有了初步印象，接下来我会继续努力！！！

Thanks♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见！！！