双指针--优选算法

个人主页：敲上瘾-CSDN博客

个人专栏：游戏、数据结构、c语言基础、c++学习、OJ题

前言：

该篇文章我们主要来学习的是双指针算法，对于该类算法我们可以直接来做题，从题中去感知该算法的魅力，最后再从题中做总结。接下来我准备了3道题，每道题会分为三个步骤讲解，分别是题目解析、算法原理、代码编写去讲解，最后再做总结。

一、移动零

1.题目解析

2.算法原理

3.代码编写

二、盛水最多的容器

1.题目解析

2.算法原理

(1)、解法一（暴力枚举）：

(2)、解法二（利用单调性）：

3.代码编写

三、快乐数

1.题目解析

2.算法原理

3.代码编写

四、总结

一、移动零

1.题目解析

该题的题目要求把数组中的零全部移到右边，并且保持非零元素的相对位置不变，这里举例了个例子[ 0，1，0，3，12]，移动后[1，3，12，0，0]，原本非零元素的数据顺序是1在前2其次最后是12，修改后的数据同样保持1在前2其次最后是12的顺序，只是把零元素移动到最后面。

2.算法原理

在我们在讲算法原理的时候要注意一个前提条件：不复制数组。

该题我在这里把它归类为数组划分的类型，也就是给定一个规则，然后依这个规则把数组里的元素划分出不同的区间，如：此问题可以理解为把混乱的数据划分为零区间与非零区间，区间与区间之间可以用指针把它们分开。

注意这里说的指针并不是真的指针，而是数组的下标，双指针只是一种思想。

一个指针可以分两个区间，但是刚开始元素是混乱的，并不能一次性把它处理完，所以还需要一个区间来存放待处理的元素，那么就需要用两个指针来把区间分开，如下：

这里可以让p1指向非零区间的最后一个元素，p2指向待处理区间的第一个元素，这样的话如果p2遍历到非零元素的话就可以直接与++p1后交换元素。而如果p2遍历到零元素的话并不需要做任何改动，p2继续遍历。那么随着p2遍历结束整数组就只剩下非零区间和零区间，而且非零元素的相对顺序依旧不变。这样这个算法就算完成了。

3.代码编写

class Solution {
public:void moveZeroes(vector<int>& nums) {int p1=-1,p2=0;while(p2!=nums.size()){if(nums[p2]!=0)swap(nums[++p1],nums[p2]);p2++;}}
};

涉及用双指针划分数组的还有快速排序的核心部分，如下：

二、盛水最多的容器

1.题目解析

该题目的意思是给一个数组，数组的下标代表柱子的横坐标，下标对应的元素代表着高度，选择两个柱子，两坐标相差的值作为容器长度，而选纵坐标最小的作为容器高度。然后构成一个容器，宽乘以高表示容器的储水量，如下：下标3和7的柱子的储水量。

2.算法原理

(1)、解法一（暴力枚举）：

该题最容易想到也是最容易理解的应该就是暴力枚举了，直接用两层循环一一枚举并更新容器最大容量。时间复杂度为O(N^2)，效率比较低在这里就不再多讲我们直接来看解法二。

(2)、解法二（利用单调性）：

因为坐标是从左往右单调增的，所以首先选定围成宽度最宽的两个柱子，然后记录它们容器容量，如下图所示：

现在围成的容量并不一定是最大的，但通过观察很容易发现如果我们把right往左挪动容器容量必然会减小，因为right往左挪动后宽度是必然会减小的，而根据题目要求高度只能取较小那个，即取的高度小于等于1。所以我们可以根据这个性质减少不必要的枚举，只让指向较小的那个元素1的left往右移，然后记录容量。

通过以上发现的性质我们就可以设计算法了，首先用left指针指向0下标，right指针指向最后一个元素的下标，然后计算并更新最大容量。如果left指向元素较小那么left右移，如果right指向元素较小那么right左移，然后计算并更新最大容量。循环进行直到left与right相遇，最后返回最大容量。

3.代码编写

class Solution {
public:int maxArea(vector<int>& height) {int sum=0,left=0,right=height.size()-1;while(left!=right){sum=max(sum,(right-left)*min(height[left],height[right]));if(height[left]<height[right]) left++;else right--;}return sum;}
};

三、快乐数

1.题目解析

该题目的意思是给定一个数然后把它的各个位数平方相加生成一个新的数，然后再次对这个新的数的各个位数的平方相加生成新的数，循环往复操作直到这个数变成1返回true或者根本变不到1返回false。如上19，它的个位数的平方加十位数的平方得到新的数82，继续对82进行同样的操作直到能够判断它是否能变为1。

2.算法原理

该题的重难点就在于如何判断该数能不能变为1，在题目中有一个要点：重复该操作可能使这个数变为1，也可能进入无限循环。而这个数变到1后继续操作也是无限的循环。

出现循环我们就很容易想到用快慢指针处理追击问题，这个思想这里也同样适用，把每次操作当做指针移动。

把两个指针放入循环内，单趟循环内快指针fast操作两次，慢指针slow操作一次，那么当数据进入循环后，fast必然会与slow相遇（即数据相等），如果此位置为1那么这个数就能变成1返回true，如果不是则不能变成1返回false。

3.代码编写

class Solution {
public:int _isHappy(int m){int sum=0;while(m){sum+=(m%10)*(m%10);m/=10;}return sum;}bool isHappy(int n) {int fast=n,slow=n;do{fast=_isHappy(fast);slow=_isHappy(_isHappy(slow));}while(fast!=slow);return fast==1;}
};