C++算法学习专题：双指针

        在一个好的程序设计是离不开一个良好的算法的。今天我们将开始新的篇章学习，深入学习算法思想。

        本篇中我们将深入学习一种比较经典的算法思想：双指针

目录

双指针算法概述

基本工作原理

1、移动零

2、复写零

3、快乐数

4、盛水最多的容器

5、有效的三角形个数

6、和为S的两个数字

7、三数之和  

8、两数之和

 9、四数之和

---

双指针算法概述

        双指针(Two Pointers)是一种非常实用且高效的算法思想，主要用于处理线性数据结构（如数组、链表等）中的特定问题。这种技术通过使用两个指针（或索引）在数据结构中协同遍历，能够显著优化算法的时间复杂度。

基本工作原理

        双指针算法通常有以下几种工作模式：

1. 同向移动指针：两个指针从同一端出发，以不同速度向同一方向移动
2. 相向移动指针：两个指针分别从两端出发，向中间靠拢
3. 固定间隔指针：两个指针保持固定距离移动，常用于滑动窗口问题

接下来我们借助一些题目题目来深入学习双指针算法思想

1、移动零

        根据题目我们知道，我们需要将所有的0全部移动到数组的末尾处，且不允许开辟新的数组来进行（原地修改）

        这类题目可以叫做“数组划分”。

        这道题实际上是利用数组下标来充当双指针

        两个指针的作用：

        cur：从左向右遍历数组 

        dest：已经处理的元素的非0元素的最后一个位置

        cur会将数组分为两个部分。左侧已经被处理了，右侧未被处理

        dest在处理过的区域内又被分为两个部分，左侧为非0，右侧为0

        三个区间

        [0.dest] 

        [dest+1,cur-1]

        [cur,n-1]       

        接下来我们将解析cur从左向后遍历的过程

        1、cur没有遇到0

        dest+1，然后交换两个指针的元素（swap函数）

        2、cur遇到0

        cur++

        代码：

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

2、复写零

 先根据异地操作然后优化为原地操作。

         当cur为非0 的时候直接写下来；当cur为0的时候0写两次。当dest到边界的时候停止。

        步骤：

        一、先找到最后一个“复写” 的数字

        1.判断cur的值

        2决定dest向前走一步还是两步

        3.判断dest是否结束

        4.cur++

        5.特殊情况下处理边界情况：n-1修改为零，随后dest向前两部，cur向前一步

        二、从后向前完成复写操作

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n=arr.size();int dest=-1, cur=0;//找到最后一个复写的数while(cur<n){if(arr[cur]==0){dest+=2;}else{++dest;}if(dest>=n-1){break;}++cur;}//处理边界情况if(dest==n){arr[n-1]=0;cur--;dest-=2;}//从后向前进行复写while(cur>=0){if(arr[cur]!=0){arr[dest--]=arr[cur--];}else{arr[dest--]=0;arr[dest--]=0;cur--;}}}
};

3、快乐数

        

快乐数可以参照下图

上面的是快乐数，下面的不是快乐数。

        类似于双向循环链表是否成环的问题。

         应用快慢双指针：

        1.定义快慢指针

        2.快指针一次走两步，慢指针一次走一步。

        3.判断相遇的值即可

class Solution {
public://返回每一位数字的平方和int Lsum(int n){int sum=0;while(n!=0){int res=n%10;//余数sum+=res*res;n/=10;}return sum;}bool isHappy(int n) {int slow=n,fast=Lsum(n);while(slow!=fast){slow=Lsum(slow);//慢指针走一步fast=Lsum(Lsum(fast));//快指针走两步}return slow==1;}
};

4、盛水最多的容器

        这道题理论上可以依赖于暴力解法解题，但是在这道题里肯定会超时，所以我们不要用这个方法来解决

        利用单调性使用双指针解决问腿。

        定义两个指针，列于两端向中间遍历，直到相遇为止。

class Solution {
public:int maxArea(vector<int>& height) {int left=0,right=height.size()-1,s=0;while(left<right){int V=min(height[left],height[right])*(right-left);s=max(s,V);//移动指针if(height[left]<height[right]){left++;}else{right--;}}return s;}
};

5、有效的三角形个数

 

        根据以前学习到的数学知识我们知道，符合三角形的三条边的条件为：任意两边之和大于第三边，任意两边之差小于第三边

        先对整个数组进行优化：对整个数组进行排序

        利用单调性使用双指针来解决。

        1.先固定最大的数:

        定义两个指针，左侧的指向最小值，右侧的指向倒数最大的数值

        如图所示，如果a+b>c，则b右侧所有的都符合情况；若不符合，则a向后，接着进行判断 

        2.在最大的数左区间内使用双指针算法快速统计出符合条件的三元数

class Solution {
public:int triangleNumber(vector<int>& nums) {//排序来进行优化sort(nums.begin(),nums.end()); //利用双指针int ret=0,n=nums.size();//先固定最大的数字for(int i=n-1;i>=2;i--){//利用双指针快速统计符合要求的三元数个数int left=0,right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){ret+=right-left;right--;}else{left++;}}}return ret;     }
};

6、和为S的两个数字

        利用数组有序和单调性的特性，使用双指针的方法。

        先对数字进行排序，随后利用双指针的方法。

如上图所示。当最大和最小相加大于目标值的时候，右值向前；小于目标值的时候左值向后。

//力扣原题目：和为S的两个数字
//本题是因为力扣上没有找到对应的题目无奈只能写在Vs上了，还请谅解
class Solution {
public:vector<int>twoSum(vector<int>& nums, int target){int left = 0, right = nums.size() - 1;while (left < right){int sum = nums[left] + nums[right];if (sum == target){return { nums[left],nums[right] };}else if (sum < target){left++;}else{right--;}}//照顾编译器的后果return -1;//没找到结果就返回-1；}
};

7、三数之和  

       

        排序＋双指针

        1.排序

        2.固定一个数a

        3.在该数字后面的区间范围内，利用双指针算法快速找到两个和为-a的数字

        细节问题：

        1.去重：找到一种结果后，left和right要跳过重复元素。用完一次双指针算法后，i也要跳过重复元素。但是一定要避免越界

        2.不漏：找到一个结果后，不断的缩小空间

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;//排序优化sort(nums.begin(),nums.end());//双指针int n=nums.size();for(int i=0;i<n;)//固定数字a{if(nums[i]>0)  break;//常数级别的小优化int left=i+1,right=n-1,target=-nums[i];//找目标值while(left<right){int sum=nums[left]+nums[right];if(sum>target) right--;else if (sum<target) left++;else {ret.push_back({nums[i],nums[left],nums[right]});//二维数组left++,right--;//去重left和rightwhile(left<right&&nums[left]==nums[left-1])  left++;while(left<right&&nums[right]==nums[right+1])  right--;}}//对i来进行去重 i++;while(i<n&&nums[i]==nums[i-1]) i++;}return ret;}
};

8、两数之和

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int left=0,right=nums.size()-1;//排序优化vector<int>arr=nums;sort(arr.begin(),arr.end());while(left<right){int sum=arr[left]+arr[right];if(sum==target)  {break;}else if(sum<target)  {++left; }else if(sum>target){--right; }  }//还原旧数组的下标int x = arr[left], y = arr[right];left = right = -1;for (int k = 0; k < nums.size(); ++k) {if (nums[k] == x &&  left== -1)left = k;if (nums[k] == y)right = k;}return { left, right };}
};

 9、四数之和

        思路类似于三数之和

        1、依次固定一个数字a

        2、在a后面的区间内，利用“三数之和”等于target-a即可

        3、在a后固定一个b，利用“双指针‘等于target-a-b即可

        不重不漏

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;//排序优化sort(nums.begin(),nums.end());int n=nums.size();for(int i=0;i<n;)//固定数a{//利用三数之和for(int j=i+1;j<n;)//固定数b{//双指针解法int left=j+1,right=n-1;long long  aim=(long long )target-nums[i]-nums[j];while(left<right){int sum=nums[left]+nums[right];if(sum>aim)  right--;else if(sum<aim) left++;else   {ret.push_back({nums[i],nums[j],nums[left++],nums[right--]});//去重left 和rightwhile(left<right&&nums[left]==nums[left-1])  left++;while(left<right&&nums[right]==nums[right+1])  right--;}}//去重jj++;while(j<n&&nums[j]==nums[j-1])  j++;}//去重ii++;while(i<n&&nums[i]==nums[i-1])  i++;}return ret;      }
};

        本篇关于双指针算法的学习只是一个入门，借助题目来学习并且了解双指针的算法思想。

        后续我们将深入学习其他算法思想。

        求一个点赞谢谢