目录
1、双指针遍历分割:避免开空间，原地处理
2、快慢指针：循环条件下的判断
3、左右指针（对撞指针）：分析具有单调性，避免重复计算
双指针又分为双指针遍历分割，快慢指针和左右指针
1、双指针遍历分割:避免开空间，原地处理
（概念）核心思想：将数组分为两端、已处理的的部分，未处理的部分，cur遍历数组，指向未完成的数组，同时处理数组元素。dest指向处理完成的部分。
算法实际操作：cur指向第一个待处理的元素。dest指向处理完元素存放的位置，根据 cur指向数据的类型，进行不同操作。
例题：移动零
1089. 复写零 - 力扣（LeetCode）
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n=nums.size();
for(int cur=0,dest=-1;cur<nums.size();){
if(nums[cur]){//非0的顺序不变，那么按序处理非0
swap(nums[cur],nums[++dest]);
}
cur++;
}
}
};class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur=0,dest=-1,n=arr.size();
while(cur<n){
if(arr[cur]) dest++;
else dest+=2;
if(dest>=n-1) break;
cur++;
}
if(dest==n){
arr[n-1]=0;
dest=n-2;cur--;
}
while(cur>=0){
if(arr[cur]) arr[dest--]=arr[cur--];
else{
arr[dest--]=0;
arr[dest--]=0;
cur--;
}
}
}
};2、快慢指针：循环条件下的判断
核心思想：经过分析，对于存在循环情况的问题，我们可以设置快慢指针来处理
.快乐数ss
class Solution {
public:
int bitsum(int n){
int sum=0;
while(n){
int i=n%10;
n/=10;
sum+=i*i;
}
return sum;
}
//快慢指针，不论是否是快乐数，都会进入循环，要不循环1为快乐数，要不是一堆数依次循环
bool isHappy(int n) {
int slow=n,fast=bitsum(n);
while(slow!=1){
slow=bitsum(slow);
fast=bitsum(bitsum(fast));
if(slow==fast&&slow!=1)
return false;
}
return true;
}
};快乐数：分析可知必存在循环，分为1循环和多个数循环，然后利用快慢指针在循环中的前进速率不同，若相遇，判断循环数为多少，即可判断是否是快乐数
3、左右指针（对撞指针）：分析具有单调性，避免重复计算
核心思想：在暴击解法上，利用单调性，避免重复计算，
11. 盛最多水的容器 - 力扣（LeetCode）
class Solution {
public:
int maxArea(vector<int>& height) {
int n=height.size();
int left=0,right=n-1;
int ret=(right-left)*min(height[left],height[right]);//记录最大值
while(left<right){
if(height[left]<=height[right]){
left++;
}else{
right--;
}
ret=max(ret,(right-left)*min(height[left],height[right]));
}
return ret;
}
};实现操作：定义左右指针，left=0，right=n-1，ret=H*W，left和right向中间靠近的话，w一定减小，h只有增大才能实现ret变大。
611. 有效三角形的个数 - 力扣（LeetCode）
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur=0,dest=-1,n=arr.size();
while(cur<n){
if(arr[cur]) dest++;
else dest+=2;
if(dest>=n-1) break;
cur++;
}
if(dest==n){
arr[n-1]=0;
dest=n-2;cur--;
}
while(cur>=0){
if(arr[cur]) arr[dest--]=arr[cur--];
else{
arr[dest--]=0;
arr[dest--]=0;
cur--;
}
}
}
};暴力枚举三层循环
简化：排序后，固定两个值——三角形中较大的那两个，然后移动较小的那个值，变成求在某一有序区间内大于某值的个数。(利用单调性)
LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int n=price.size();
int low=0,height=n-1;
while(low<height){
if(price[low]+price[height]<target){
low++;
}else if(price[low]+price[height]>target){
height--;
}
else{
break;
}
}
return {price[low],price[height]};
}
};暴力枚举+利用单调性优化：类盛水容器
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n=nums.size();
vector<vector<int>> ret;
for(int k=0;k<n-2;){
int left=k+1,right=n-1;
int target=-nums[k];
while(left<right){
if(nums[left]+nums[right]<target){
left++;
}else if(nums[left]+nums[right]>target){
right--;
}
else{
ret.push_back(vector<int>{nums[k],nums[left],nums[right]});
left++;right--;
while(left<right&&nums[left]==nums[left-1])left++;//细节问题：不重复同时判断不越界：left<right
while(left<right&&nums[right]==nums[right+1])right--;
}
}
k++;
while(k<n-2&&nums[k]==nums[k-1])k++;
}
return ret;
}
};18. 四数之和 - 力扣（LeetCode）
类上，对内两层的暴力改为求目标值
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n=nums.size();
sort(nums.begin(),nums.end());
vector<vector<int>> ret;
for(int x=0;x<n-3;){//固定第一个数
for(int k=x+1;k<n-2;){//固定第二个数
long long targeti=(long long)target-(nums[x]+nums[k]);
for(int left=k+1,right=n-1;left<right;){
long long sum=nums[left]+nums[right];
if(sum>targeti){
right--;
}else if( targeti>sum){
left++;
}else{
ret.push_back(vector<int>{nums[x],nums[k],nums[left],nums[right]});
left++;
right--;
while(left<right&&nums[left]==nums[left-1]) left++;//注意仅仅，找到target去重，未找到的话，前面那个值未被统计不同去重
while(left<right&&nums[right]==nums[right+1]) right--;
}
}
k++;
while(k<n-2&&nums[k]==nums[k-1]) k++;
}
x++;
while(x<n-3&&nums[x]==nums[x-1]) x++;
}
return ret;
}
};
