当前位置：首页 > news >正文

算法篇-------------双指针法

news 来源：原创 2025/7/3 9:47:09

温馨提示：由于c++语言在编程上更有优势，更加简洁，本文代码均为c++代码，其他语言也可以做，思想是不变的！

1.应用场景

涉及到对数组的操作的题目，可以考虑双指针方法解决

2.基本框架

根据其名字不难想出，我们是设置两个“指针”，但由于我们是对数组进行操作，为此，我们可以模拟指针的应用，用下标来访问数组，设置；两个变量cur和dest,其中，一个由于遍历数组，判断情况，另一个用于我们的一些根据题目而进行的特殊操作

值得注意的是，双指针不一定非要从前向后移动，可能会从数组末尾或者其他位置开始移动，具体的要看题目要求！

3.题目示例

3.1 移动0

283. 移动零 - 力扣（LeetCode）

这个题要求我们对数组中的零进行移动，属于对数组的操作，可以用双指针来解决，那么应该如何解决呢？

解决思路：

不难想到，我们可以用cur遍历数组，开始的时候可以将cur放置在数组首元素的位置，dest置于-1的位置，之后让cur遍历数组，由于题目想让我们将0都移到后面去，因此，我们就要找到非零元素，让cur指向他，同时dest要指向0，之后将二者swap一下，在同时++，之后再循环进行上述操作，cur遇到零继续++，遇到非零就停下来和dest交换，直到cur走完了整个数组

参考代码：

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

3.2 复写0

1089. 复写零 - 力扣（LeetCode）

这个题要求我们对0进行复写，并且最终数组元素的个数还要保证不变，这就意味着只要原数组里面出现了0，那么就要有元素被“移出”数组，那么我们应该怎么解决这道题呢？

解决思路：

一开始我想的是从前往后，就是类比3.1题那样，但会惊奇的发现有些元素还没被cur遍历到就被改成0了，此种想法失败，所以我们便考虑逆其道而行之，从后面往前遍历，但是现在问题就是，我怎么找到我最后一个复写的元素？

直接盲目凭空猜是肯定不靠谱的，我们不妨这样，可以进行两轮的双指针操作，第一轮就是用来寻找最后一个复写的元素，第二轮在去进行复写。

我们寻找过程如下：我们第一轮可以模拟复写操作，只遍历，不复写，先将cur==0，dest==-1，之后遇到非零元素，就同时++，遇到0元素，就cur++,dest++两次，当dest到最末尾时，cur便指向了最后一个复写的元素

但是还有一种特殊情况，比如数组为【1，0，2，3，0，4】，按照上述操作会使dest超出边界，为此我们要处理一下：直接让arr[n-1]=0,cur--,dest-=2

当我们找到最后的复写元素后，从后往前复写，cur指向的为0，就进行两次将dest位置元素赋值为0并--，同时cur--,当cur指向的为非0，就arr[dest--]=arr[cur--]就行了

参考代码：

class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur=0,dest=-1,n=arr.size();//寻找最后一个复写元素for(cur=0;cur<n;cur++){if(arr[cur])dest++;elsedest+=2;if(dest>=n-1)break;}//处理特殊情况if(dest==n){arr[n-1]=0;cur--;dest-=2;}//从后往前进行复写while(cur>=0){if(arr[cur])arr[dest--]=arr[cur--];else{arr[dest--]=0;arr[dest--]=0;cur--;}}}
};

3.3 快乐数

202. 快乐数 - 力扣（LeetCode）

这个题要求我们寻找快乐数，很明显这是一个定义题，需要我们了解明白定义后在去将其解决

解决思路：

我们不妨就按照题目里面说的做，画出图来可以更好的帮我们解决问题，当测试用例为19时，

19---->82---->68----->100

当测试用例为2时

我们会发现这是一个环！但是我们仔细想一下，上面那个符合的不也是个环吗？只不过环的值都为1！而由鸽巢原理（抽屉原理）我们知道，这个数是一定带环的（了解就好，不是重点）。所以我们得出了解决思路，只要判断相遇点（入环点）是否为1就行了。有一定基础的朋友或许会想到快慢指针的方法，没错，本题正是快慢指针的解法！只不过我们还是模拟指针的方法，在链表那里我们是使用真的指针，而在这里我们直接让指针变为数就好，比如当测试用例为2时，让slow=2，之后直接让slow=2^2=4,之后在slow=4^2=16,以此类推！

为了方便起见，我们可以写一个函数，用于计算下一个数是什么，以便于“指针”的移动。

参考代码：

class Solution {
public:int sum(int n)                    //计算下一个数{int total=0;                  //局部变量要初始化，否则就是随机数，会影响后面+=操作while(n){   int t=n % 10;total+= t * t ;n/=10;}return total;}bool isHappy(int n) {int slow=n;int fast=sum(n);      //让fast指针指向下一个数while(slow!=fast){slow=sum(slow);fast=sum(sum(fast));}return slow==1;}
};

3.4 装水最多的容器

11. 盛最多水的容器 - 力扣（LeetCode）

这个题要求我们寻找体积最大的一个区间，那么我们应该怎么找呢？

解决思路：

方法一）暴力求解：把每个体积都算出来，求最大，两层for循环，但是会超出时间复杂度

方法二）找规律：我们先任意取出一段区间，不妨以【6，2，5，4】这段区间为例，先求出最边界的体积V1，之后将指针移动到高度为4的位置处，因为决定装水多少的是最低的高度，之后移动这个指针，无非会出现两种情况，首先宽度肯定是减小的了，这一点应该不需要解释，那么在移动的过程中，出现的数字可能比4大也可能比4小，如果比4小，也可以直接pass了，因为此时宽度和高度都减小了，肯定不是最大了，如果比4大，就算一下体积，用max()函数取一个最大值，之后重复上述操作，如果等于4的也可以直接Pass，那现在我们可以把范围放大了，用在整个数组上了。

参考代码：

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

3.5 有效三角形个数

611. 有效三角形的个数 - 力扣（LeetCode）

这道题给定我们一个数组，要求我们统计可以组成三角形的个数

解决思路：

方法一）暴力破解：利用三层for循环，时间复杂度为O（N^3)，可能会超出时间复杂度

方法二）双指针法：我们知道，三角形两边之和大于第三边，我们可以利用这个性质，先将数组排成升序，在固定住最大的数（最后一个数），并设立两个指针，一个指向下标0的位置，一个指向倒数第二个位置，之后将这两个位置上的数相加，会出现两种结果（为方便起见，左边的数我称之为a，右边的数我称之为b):a+b>c以及a+b<=c，对于第一种情况，由于数组是有序的，从a到b是升序的，由于a+b已经大于c了，而a在这里面是最小的数，所以[a,b]内所有的数一定符合要求，由于我们是a+b>c，所以我们要减小相加的值，为此我们让right--，而对于第二种情况，由于b已经是这里面最大的数了，但是a+b还是小于等于c，说明区间[a,b]的所有数都无法构成三角形，因此我们要让left++，扩大一下相加的和，当left<right条件走完时，重新确定最大的数，重复上述步骤

参考代码：

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--)     //最大的数只能到下标为2的位置{int left=0,right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){ret+=right-left;right--;}else{left++;}}}return ret;}
};

3.6 查找目标值

LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

这个题要求我们在数组内找一对和为目标值的数，解题思路如下

解题思路

方法一）暴力破解：两层for循环，时间复杂度O（N^2),会超时

方法二）双指针法：我们还是一个指针放在下标为0的地方，另一个放在末尾，之后看这两个数的和并于目标值比较，会出现三种情况：

1）等于目标值：这种情况是我们想要的，直接返回这两个数就ok了

2）小于目标值：由于我们的数组是递增的，所以我们要增大我们这个数组的和，因此要left++

3）大于目标值：由于我们的数组是递增的，所以我们要减小我们这个数组的和，因此要right--·

参考代码：

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int left=0;int right=price.size()-1;while(left<right){int sum=price[left]+price[right];if(sum>target){right--;}else if(sum<target){left++;}else{return {price[left],price[right]};}}}
};

提交时会发现报错：

报错信息是：并不是所有的路径都有返回值，因此我们为了照顾编译器，给加上一些返回值

所以正确的代码应该是：

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int left=0;int right=price.size()-1;while(left<right){int sum=price[left]+price[right];if(sum>target){right--;}else if(sum<target){left++;}else{return {price[left],price[right]};}}return {-1,-1};    //这个-1是我规定的，读者可以换成喜欢的数字，只要别影响程序即可}
};

3.7 三数之和

15. 三数之和 - 力扣（LeetCode）

这道题要求我们在数组里面找三个数，而且不能重复，并且他们的和要等于0，这道题的解决思路可以依赖于上一步做延申。

解题思路：

这道题我们还是采取双指针的方法来做题，但是我们却要找三个变量，因此我们需要先固定住一个，再去寻找另外两个，~~类似于化学的同分异构体的固一动二法，~~由于题目不要求我们对顺序有要求，所以我们可以先将数组进行排序，这样方便我们查找，而且也符合题目的要求，我们不妨将它排为升序之后，从左到右依次固定，再设置两个指针，一个指针指向这个数组的最末尾，而另一个指针则指向固定数的下一个数。而由指针指向的这两个数相加之后，我们想要的结果是等于固定的数的相反数，这样才能使他们的相加结果等于零，之后的方法就可以仿照第六题，这里不再赘述。另外可以提出一个优化的点，我们的固定的数只需要小于等于零的部分即可，因为我们的数组是已经排为升序的，如果固定的数在为正数，那它和另外两个数肯定不会相加为零。还有一点值得注意的是由于答案不想出现重复的结果，所以我们对指针也可以优化，即遇到相同的数则继续++或者--。

参考代码：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;//1.排序sort(nums.begin(),nums.end());int n=nums.size();//2.利用双指针解决问题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--;}}//去重ii++;while(i<n&&nums[i]==nums[i-1]) i++;}return ret;};
};

3.8 四数之和

18. 四数之和 - 力扣（LeetCode）

这道题要求我们找四个数，并且之和为目标值，而且四个数还不要重复，其实这个题和上一个题一个思路，只不过更麻烦了一些而已

解题思路：

我们还是先将数组排序，之后先固定一个数a，这样题目就转变为了找三个数，目标值为target-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());for(int i=0;i<nums.size();)    //固定a{//三数和for(int j=i+1;j<nums.size();)//固定b{int left=j+1,right=nums.size()-1;int aim = target-nums[i]-nums[j];while(left<right){int sum=nums[left]+nums[right];if(sum<aim) left++;else if(sum>aim) right--;else{//打包，放到ret中ret.push_back({nums[i],nums[j],nums[left++],nums[right--]});//去重一while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}//去重二j++;while(j<nums.size()&&nums[j]==nums[j-1])   j++;}//去重三i++;while(i<nums.size()&&nums[i]==nums[i-1])  i++;}return ret;}
};

但是，这样会发生报错：

原因就是我们测试的数太大时，红线那里会溢出，所以我们把int改为long long就行，后面记得强转一下哈！

好了！至此，我们语法篇的第一讲------双指针到此结束，希望对读者有所帮助！我们下一篇文章再见！bye~

1.应用场景

2.基本框架

3.题目示例

3.1 移动0

3.2 复写0

3.3 快乐数

3.4 装水最多的容器

3.5 有效三角形个数

3.6 查找目标值

3.7 三数之和

3.8 四数之和

相关文章：