【算法】--双指针法

一、双指针法常见的双指针法有两种形式一种是对撞指针一种是快慢指针对撞指针对撞指针一般用于顺序结构中又称为左右指针。对撞指针一般是一个left指针从左边往右边移动然后一个right从右边往左边移动然后两个指针就都向中间进行逼近。对撞指针的终止条件一般是两个指针相遇或者错开或者是在循环中已经找到需要的答案就跳出循环其常用的循环条件如下leftright(是否需要等这个要具体问题进行分析)leftright快慢指针又称为龟兔赛跑游戏其基本思想就是使用两个移动速度不同的的指针在数组或者链表等序列结构上移动这个方式经常用于处理环形链表和数组非常有用然后对于问题出现了循环反复的情况那么我们都可以考虑一下快慢指针的思路快慢指针的方式有很多种其最常用的一种就是在一次循环中每次让慢的指针向后移动一位而块的指针向后移动两位实现一块一慢的情况如上就是我们双指针法的思想了。下面我们来进行题目的讲解。二、题目讲解1、移动零题目链接力扣283移动零首先我们对题目进行分析题目给我们一个数组然后要求将数组中的零元素都放在数组的后面而且不可以改变非零元素的相对顺序这是啥意思呢就比如示例1中原来的非零数据的顺序是1-3-12的这个顺序那么我们移动完也要保持这个相对顺序。要是没有后面的必须在不复制数组的情况下原地对数组进行操作那么我们可以创建一个和原数组一样大小的数组然后使用一个循环遍历原数组将非零的元素先插入到创建的数组然后再将零填入。解法这个解法有点用到我们的快速排序的思想我们创建两个整型都是表示数组的下标slow和fast指针fast做为探路的走在slow的前面然后fast遇到非零的数那么slow就然后将slow和fast的元素进行交换遇到零的情况fast就继续往前找直到fast走到了数组的最后一个元素那么就搞定了。我们可以发现我们将[0slow]这个区间的数据都保证是非零的数据。下面我们通过一个数组演示一遍示例1{010312};然后我们的fast初始为0slow初始为-1为啥是-1是初始我们的默认数组全是零元素所以数组中还没有非零元素所以是-1。然后还是进入循环循环条件fastnums.size()。第一步遇到是0那么fast然后遇到的是1那么slow然后swap(nums[slow],nums[fast]);交换完后fast。代码如下class Solution { public: void moveZeroes(vectorint nums) { int fast0; int slow-1; int nnums.size(); while(fastn) { if(nums[fast]!0){ slow; swap(nums[slow],nums[fast]); } fast; } } };2、复写零题目链接力扣1089复写零题目描述先对题目进行分析首先是传入一个数组然后要求我们将数组中的零元素进行复写复写的要求是就在零元素的后面进行复写就比如我们的示例1然后要求数组最后不可以超过原来数组的长度然后要在原数组上进行修改。解法一首先我们很容易想到的一个方式就是遍历数组然后找零元素找到零元素后记录当前位置的后一个位置的元素然后将后一个位置进行插入零然后零后面的元素都往后挪动一位要是控制好别越界就行。class Solution { public: void duplicateZeros(vectorint arr) { int n arr.size(); // 遍历数组注意每处理一个0后i需要额外1跳过新写入的0 for (int i 0; i n; i) { if (arr[i] 0) { // 从数组末尾向前将i之后的元素整体右移1位 for (int j n - 1; j i; --j) { arr[j] arr[j - 1]; } // 在i1位置写入0复写 if (i 1 n) { // 防止越界 arr[i 1] 0; } // 跳过刚写入的0避免重复处理 i; } } } };代码如上时间复杂度为O(n^2)。那么下面是使用我们的双指针的方式进行更高效率的解题。解法二我们可以创建两个指针cur和dest然后我们的fast先遍历数组然后当curn就一直执行循环然后每次遍历判断cur这个位置此时的数据其有两种情况1、arr[cur]0那么dest2cur2、arr[cur]!0那么dest、cur然后判断此时的dest是否到数组结束的位置如果到达那么就结束循环如果没有那么cur继续。然后循环结束那么cur此时前面的位置就是我们要复写的元素了。复写的逻辑如下如果arr[cur]0那么arr[dest]0arr[dest-1]0dest-2cur--如果arr[cur]!0那么arr[dest]arr[cur]dest--cur--代码如下可以看到运行是报错的这是因为我们上面产生了越界访问所以我们要对于越界的情况进行处理其越界产生的特殊情况就是当我们要复写的第一个元素就是零那么会导致dest变成n那么就会产生对数据的越界访问。所以我们对于这种清理特殊处理一下:class Solution { public: void duplicateZeros(vectorint arr) { int cur0; int dest-1; //找到最后一个要复写的数据 while(curarr.size()) { if(arr[cur]0){ dest2; } else{ dest; } if(destarr.size()-1){ break; } cur; } //处理越界情况arr[n-1]0的情况 if(destarr.size()){ arr[arr.size()-1]0; dest-2; cur--; } while(cur0) { if(arr[cur]0){ arr[dest--]0; arr[dest--]0; } else{ arr[dest--]arr[cur]; } cur--; } } };3、快乐数题目链接力扣202快乐数题目描述给我们一个整数让我们判断其是否为快乐数那么我们看看快乐数是啥意思就是说给我们一个整数然后其每个位上面的数的平方相加相加后的话要是为1那么就是快乐数要是没有变成1那么就会循环执行。那么其循环执行最终也是两种结果最后变成1那么是快乐数无限循环始终到不了1。首先对于是快乐数的情况就很简单了我们只需要对于进行一个循环然后使其的每个位次的数进行平方相加即可。然后对于不是 快乐数我们使用示例2中的数据来看看是咋样的。n2第一次循环2^204第二次循环4^2016第三次循环1^26^237第四次循环3^27^258第五次循环5^28^289第六次循环8^29^2145第七次循环1^24^25^242第八次循环4^22^220第九次循环0^22^24我们发现第九次循环后那么就会回到第一次循环的结果那么就从这里开始造成死循环。那么就很像形成一个环的感觉。那么我们不妨大胆的猜测一下其大概率就是这个情况不然题目为啥给一个这个示例。实际上确实是这样我们看看题目中的最大值是2^31-14294967295那么我们算9999999999的值。81*10810那么我们可以得到的结论是这个范围的数据这么算的结果就是在[1810]这个区间。那么我们假设最坏的情况每次循环的结果都是不一样的那么其运行811次那么其中肯定也会有一样的情况所以出现死循环的情况其一定是一个环。那么我们可以使用我们的快慢指针来解决这个问题。当我们的指针相遇的时候循环退出然后判断当前值是否为1如果为1那么就是我们的快乐数如果不为1那么就不是。实际上快乐数也是形成一个环。不过这个环的入口是1出口也是1而且这个环只有1这个元素。代码如下class Solution { public: int sum(int n) { int sum0; while(n) { int tmpn%10; sumsum(tmp*tmp); nn/10; } return sum; } bool isHappy(int n) { int slown; int fastsum(n); while(slow!fast) { slowsum(slow); fastsum(sum(fast)); } if(slowfastslow1fast1){ return true; } else{ return false; } } };4、盛最多水的容器题目链接力扣11盛最多水的容器题目描述题目中给一个数组然后数组的元素就是表示高然后让我们找可以组成最大容量的容器的组合。然后我们容器的底部是元素之间的距离。就比如我们上面图中的第二个和第九个元素之间的这个容器那么其底部宽就是两个元素的下标的差。解法一首先我们很快可以想到的一个解法暴力枚举将每个元素的所有配合进行计算然后找到最大的容量。class Solution { public: int maxArea(vectorint height) { int left 0, right height.size() - 1; int maxWater 0; while (left right) { int currentWater min(height[left], height[right]) * (right - left); maxWater max(maxWater, currentWater); // 移动较短的那条边尝试获得更高的有效高度 if (height[left] height[right]) { left; } else { right--; } } return maxWater; } };上面代码虽然编译通过了但是其时间复杂度达到了O(n^2)所以效率还是很慢的。下面我们讲解一个更优的解法。解法二我们创建左右指针left和ringht。那么容器的容量的计算如下Vmin(arr[left],arr[right])*(ringht-left)那么我们左右指针进行移动的时候首先宽是一定会改变的而且是变小的。要是我们挪动的是高度大的那个边界的指针那么如果大的那个指针挪动后的元素比现在小的那个边界还要小那么就会更小然后要是挪动到元素要更大的但是min也还是原来那个小的边界所以这个挪动只会将容量变小。我们再看看挪动的是小的那个边界的那么其要是挪动到大的元素那么就会导致min变大从而才有可能会使得容量变大。综上所述我们计算完后我们比较两个边界的值谁小就挪动谁。代码如下class Solution { public: int maxArea(vectorint height) { int left 0; int rightheight.size()-1; int ret0;//表示最大的容量 while(leftright) { int hmin(height[left],height[right]); int vh*(right-left); retmax(ret,v); if(height[left]height[right]){ left; } else{ right--; } } return ret; } };5、有效三角形的个数题目链接力扣611有效三角形的个数题目描述如下我们来分析一下题目首先对于有效的三角形就是我们的任意两边之和要大于第三边。不过其实我们不需要去比三次我们只需要保证最小的两个边大于第三边即可。首先我们可以使用暴力枚举的方式进行解答就将所有的情况列出来判断即可。下面我们来看看效率更高的解法。我们先将数组进行排序使其成为升序。然后我们固定最大值然后我们创建两个指针然后一个指针在最左端走一个在最大值的前面一个位置开始走然后我们一直判断两个位置的元素相加是否大于最大值要是大于那么说明这个此时right位置的这个元素和left到right-1这个区间的元素相加都是大于这个最大值第三边的。如果小于那么我们就对left然后大于我们就继续调整right的位置。class Solution { public: int triangleNumber(vectorint nums) { sort(nums.begin(),nums.end()); //先将数组进行排序 //双指针法 int count0; int nnums.size(); for(int maxn-1;max2;max-- ){ int left0; int rightmax-1; while(leftright) { if((nums[left]nums[right])nums[max]) { countright-left;//left这个位置都可以那么left1到right这个区间也可以 right--; } else{ left; } } } return count; } };6、查找总价格为目标值的两个商品题目链接两数之和题目描述其实这个问题挺简单的看它说了一大堆其实就是在这个数组中找到两个数相加是等于target的。而且题目说了数组还是有序的所以就省了我们再去排序我们创建两个指针一个再数组的尾往回走一个在开头往尾部走。然后我们将其相机和要求的值进行比较如果大了那么right--如果小了那么left。然后循环终止的条件是left和right相遇了。代码如下class Solution { public: vectorint twoSum(vectorint price, int target) { int left0; int rightprice.size()-1; while(leftright) { int tmpprice[left]price[right]; if(tmptarget){ return {price[left],price[right]}; } else if(tmptarget){ right--; } else{ left; } } return {-1,-1}; } };7、三数之和题目链接两数之和题目描述这个和我们的两数之和大差不大我们可以先将一个值固定住那么不就变成了我们的两数之和了嘛。但是题目又加了一个要求就是要求答案中不可以有重复的三元组。首先就是我们可以借助C的容器来去重。然后我们还有更加高效的方式我们可以在遇到三数之和满足要求后对于数据的挪动的时候然后判断这个位置的数据是否和刚刚那个位置的数据一样如果一样那么就再挪动。那么这样操作我们就完成了我们的手动去重。要注意的是我们固定的那个值也要去重处理。代码如下class Solution { public: vectorvectorint threeSum(vectorint nums) { vectorvectorint v; sort(nums.begin(),nums.end()); for(int i0;inums.size()-2;) { if(nums[i]0){ break; } int lefti1; int rightnums.size()-1; int ret-nums[i]; while(leftright) { if(nums[left]nums[right]ret){ v.push_back({nums[i],nums[left],nums[right]}); left; right--; while(leftrightnums[left-1]nums[left]){ left; } while(leftrightnums[right1]nums[right]){ right--; } } else if(nums[left]nums[right]ret) { left; } else{ right--; } } i; while(inums.size()-2nums[i-1]nums[i]){ i; } } return v; } };8、四数之和题目链接四数之和四数之和和前面的三数之和的方法是一样的我们先固定一个值那么这个里面就是我们的三数之和了。要注意的是我们题目也说了不能重复所以也要我们去做去重操作。代码如下class Solution { public: vectorvectorint fourSum(vectorint nums, int target) { vectorvectorint v; sort(nums.begin(),nums.end());//先将数组进行排序 int nnums.size(); int tmptarget; for(int a0;an-3;)//固定左边的 { int rettmp-nums[a]; for(int ba1;bn-2;)//找到三数之和为ret的 { int leftb1; int rightn-1; long long sum(long long)ret-nums[b]; while(leftright) { if(nums[left]nums[right]sum) { v.push_back({nums[a],nums[b],nums[left],nums[right]}); left; right--; while(leftrightnums[left-1]nums[left]) { left; } while(leftrightnums[right1]nums[right]) { right--; } } else if(nums[left]nums[right]sum) { left; } else { right--; } } b; while(bn-2nums[b]nums[b-1]) { b; } } a; while(an-3nums[a-1]nums[a]) { a; } } return v; } };