目录
接下来的日子会顺顺利利，万事胜意，生活明朗-----------林辞忧
前言
在解决关于数组的问题时，常常用到双指针的解决方法来优化算法，帮助解决问题，常见的双指针分为普通双指针，快慢指针，左右相遇指针等
一：普通双指针
普通双指针就是解决普通问题，一般是在原数组上改动数据时，有从前向后，从后向前，都从前向后，都从后向前，对数组分块来解决问题等
1.经典题目一 283移动0问题
分析
代码实现
class Solution {
public:
void moveZeroes(vector<int>& nums) {
//双指针方法
int cur=0,dest=-1;
int n=nums.size();
while(cur<n)
{
if(nums[cur]==0)
{
++cur;
}
else
{
swap(nums[++dest],nums[cur++]);
}
}
}
};2.经典题目二 1089复写0
分析
代码实现
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur=0,dest=-1;
int n=arr.size();
//求最后一个要复写的数据
while(cur<n)
{
if(arr[cur])//不为0走一步
{
++dest;
}
else//为0走两步
{
dest+=2;
}
if(dest>=n-1) break;//边界问题防止越界访问
++cur;
}
//处理边界问题
if(dest==n)
{
arr[n-1]=0;
dest-=2;
cur-=1;
}
//再从后往前复写数据
while(cur>=0)
{
if(arr[cur])
{
arr[dest--]=arr[cur--];
}
else
{
arr[dest--]=0;
arr[dest--]=0;
--cur;
}
}
}
};二：解决成环类问题-快慢指针
在解决一些关于数组或者链表成环类问题时常常用到的是快慢指针，就是slow指针走一步，fast指针一次走两步，常常用相遇来解决问题
经典例题一 202快乐数
分析
代码实现
class Solution {
public:
int bitSum(int n)//计算n的平方和
{
int sum=0;
while(n)
{
int tmp=n%10;
sum+=tmp*tmp;
n/=10;
}
return sum;
}
bool isHappy(int n) {
int slow=n,fast=bitSum(n);//slow为第一个位置，fast为第二个位置
while(slow!=fast)//走到直至相遇
{
slow=bitSum(slow);
fast=bitSum(bitSum(fast));
}
if(slow==1)//是1的话则是快乐数
{
return true;
}
return false;
}
};三：左右相遇指针
说明一下，左右相遇指针是自己理解取的名字，意思就是这类题定义的双指针得从两端向中间走，直至相遇
经典例题一 11 盛最多水的容器
分析
对于这道题大多人首先想到的是暴力求解，求出每两个数据之间的容量，在求出最大的一个
但这样的话对于这道题，这样做的话会超出时间限制的，因此得采取其他方法
代码实现
class Solution {
public:
int maxArea(vector<int>& height) {
int left=0,right=height.size()-1;//左右双指针
int ret=0;
while(left<right)
{
int v=min(height[left],height[right])*(right-left);//算出数据
ret=max(ret,v);//求出最大的一个数据，存放在ret中
//移动指针
if(height[left]<height[right])
{
++left;
}
else
{
--right;
}
}
return ret;
}
};
