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

利用双指针法解题

news 2024/10/31 2:36:53

双指针的简单介绍

双指针的类型

题目一：283. 移动零 - 力扣（LeetCode）

题目意思解释

算法原理

代码实现

题目二：1089. 复写零 - 力扣（LeetCode）

题目意思解释

算法原理

代码实现

题目三：202. 快乐数 - 力扣（LeetCode）

题目意思解释

算法原理

代码实现

题目四：11. 盛最多水的容器 - 力扣（LeetCode）

题目意思解释

算法原理

代码实现

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

题目意思解释

算法原理

代码实现

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

题目意思解释

算法原理

代码实现

题目七：15. 三数之和 - 力扣（LeetCode）

题目意思解释

算法原理

代码实现

题目八：18. 四数之和 - 力扣（LeetCode）

题目意思解释

算法原理

代码实现

双指针的简单介绍

双指针是一种常用的算法技术，主要用于处理数组、链表等线性结构中的问题。它通过使用两个指针在数据结构中同时移动，从而达到有效解决问题的目的。这种方法通常能够减少空间复杂度或时间复杂度，或者使代码更加简洁。

但是在这里的指针并非真正的指针

它可以是数组的下标，亦或是链表的第k个值。

双指针的类型

相向双指针：

两个指针分别从数组的两端向中间移动。
常用于寻找数组中两数之和、判断回文字符串、合并两个有序数组等问题。

同向双指针：

两个指针都从同一方向移动，通常一个指针移动得快，另一个移动得慢。
常用于寻找子数组、滑动窗口问题、链表环检测等。

下面我将会从8个力扣的题来讲解利用双指针来解题。

每个题将会从对题目的意思介绍，算法的原理，编写代码的注意点

有的题目机译没什么问题就不一句一句解释了

题目一：283. 移动零 - 力扣（LeetCode）

题目意思解释

该题目给了一个数组nums，然后让你编写一个函数，对数组进行操作后，使得该数组分为两部分，0全部在数组的后半部分，前半部分全为非0，并且非零部分的元素还保持着原来数组的相对位置，相对位置的意思就为：原数组中a在b前面，那么进行操作过后还是a在b前。并且，该题目还要求只能在数组的原地进行操作。

算法原理

如果我们先抛开计算机的编程思想，我们在现实生活中遇见这样问题，那么我们肯定想着先按照相对位置把所有非0元素拿出来排好，在把0依次放在其后，但是在编程中这就不是在数组原地进行操作。

经过思考后发现可以依次交换如果两个相邻的数，只需要把非0的与0进行交换。

就比如只需要先1 0交换后再 0 3，最后0 12就达到了要求，那么我们把这种思想转换为编程思想即可，这种思想就为双指针思想。

我们只需要定义两个“指针”

然后把数组分为两个区间，其中又分为三个小区间。

对于指针的操作如下：

这里用的是同向指针

代码实现

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

题目二：1089. 复写零 - 力扣（LeetCode）

题目意思解释

给了一个长度固定的整形数组，然后将所有0全部复写一边，并将其后面的所有元素全部向右移动，还需要对该数组就地修改，不返回任何东西。

算法原理

理解题目后，如果对时间复杂度比较敏感，算法就必须从后往前进行遍历。这是因为如果从前往后依次复写，可能会出现覆盖问题，并且时间复杂度将达到 O(n²)。

采用双指针算法，从后往前遍历会更加高效。以第一个测试用例为例，我们可以清楚地知道最后一个操作数是4，因此只需将4 覆盖到最后一个0 的位置，然后再依次将0复写到前面的两个位置。这样，我们可以高效地向前遍历并进行覆盖。

在实现时，可以参考第一题的代码，使用双指针的方法来完成。以下是操作示意图，具体实现可以根据这个思路进行编码。

那么重要的怎么明确找到最后一个位置，也就是怎么代码实现使其cur指针指向的是4，而不是0或者5，

那么这里是用到的快慢指针，我先直接给出代码，代码所要实现的就为

如果arr[cur]为0的话dest+=2
如果arr[cur]不为0的话dest++
dest走到最后一个元素结束
最后cur++

        int n=arr.size();int dest=-1,cur=0;while(dest<n){if(arr[cur]){dest++;}else{dest+=2;}if(dest>=n-1) break;cur++;}

在编写这部分代码时，我也有很多疑问，比如为什么将 dest 初始化为 -1 而不是0，cur 又为什么初始化为0。

要理解这些初始化的原因，从结果反推起始的设置会更加清晰。

从结果倒推，我们可以得出以下结论：因此，dest 初始化为 -1，而 cur 初始化为0。

但是根据算法原理一点点实现代码，然后运行提交，会报越界的错误，这是因为有种特殊的情况，比如下面的这个数组：

经过上面的代码后，cur与dest的指向情况如下：

因此，当 dest 等于 n 时，需要进行特别处理。

代码实现

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n=arr.size();int dest=-1,cur=0;while(dest<n){if(arr[cur]){dest++;}else{dest+=2;}if(dest>=n-1) break;cur++;}if(dest==n){arr[n-1]=0;dest-=2;cur--;}while(cur>=0){if(arr[cur]){arr[dest]=arr[cur];cur--;dest--;}else{arr[dest]=arr[cur];dest--;arr[dest]=arr[cur];dest--;cur--;}}}
};

题目三：202. 快乐数 - 力扣（LeetCode）

题目意思解释

题目的意思很好理解，那么这里我就不在解释了，我说明需要注意的地方：这个题中又这样一句话：然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1

永远的无限循环就是他题目中的2，他会陷入循环，并且循环中一直不会变为1.

但起始1也是一种循环，但他的循环一直为1.

算法原理

这道题的算法原理其实是引用了环形队列的快慢指针的思想，（题目：141. 环形链表 - 力扣（LeetCode）））

我这里举一个生活中跑步的案例解释一下：假设小明与小刚同学同时从宿舍出发去操场跑步，小明的速度是小刚速度的二倍，那么总有那么一秒初（不是一秒中也不是末）小刚与小明会相遇。

所以我们以这种的方法就可以判断是以1循环还是不规则的循环

代码实现

class Solution {
public:int bitsum(int n){int ret=0;while(n){int t=n%10;ret+=t*t;n/=10;}return ret;}bool isHappy(int n) {int slow=n,fast=bitsum(n);while(slow!=fast){slow=bitsum(slow);fast=bitsum(bitsum(fast));}return slow==1;}
};

题目四：11. 盛最多水的容器 - 力扣（LeetCode）

题目意思解释

依旧是这一题的意思很好理解，需要提一嘴的就是一个木桶所能装多少水是由其短板决定的。所以这一题的容器高是由两端木板中的短板决定。

算法原理

对于一个容器的容量计算公式 v=w*h

那么我们还是利用双指针来解决这道题，需要用到的是相向双指针，定义一个right指针，与left指针，需要解决的是什么情况left++，什么情况下right--，

从公式来说，无论是left++，还是right--，他都会使得w减小，但是w减小的话，如果v要想增加，那么只能使得h增大。然而一个容器内的h是由短板决定，所以就很容易想到要将小的那个进行调整。

这也很好理解，如果我们对高的进行调整，就算遇到一个更大的数，那么h依旧不会发生改变，遇见小的只会更小，不符合我们的要求。

代码实现

class Solution {
public:int maxArea(vector<int>& height) {int n=height.size();int r=n-1,l=0;int mx=0;while(r>l){int w=r-l;int h=min(height[r],height[l]);mx=max(mx,h*w);if(height[r]>height[l]) l++;else r--;}return mx;}
};

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

题目意思解释

同样这道题的描述依旧很详细，需要提一嘴的就是如果该数组为[ 2 , 2 , 2 , 3 , 4 ]，

那么2 , 2 ，3 与2 , 2 , 3，是不同的两个组，应该计为2，不为1。

同样需要补充的一点就是构成三角形的规定：任意两边之和大于第三边。

算法原理

我们这道题就是运用到的为任意两边之和大于第三边，但是如果将三个数都进行两两组合，就显得过于麻烦，这时候需要我们先排序，排序之后，任取三个数，相对位置的前两个数相加如果大于第三个，那么其余组合一定大于另外一边。这也很好理解，如果三个数两个小的数相加大于最大的哪一个，那么其余组合一定成立。

因为有三个操作数，那么是不是要用三指针解决呢？

其实不然，我们不妨套一层循环，定一，另外两个用双指针解决子问题。

那么需要解决的就是定谁？

令两个小的数为 a ，b，最大的为 c ，如果a+b>c则构成三角形

如果定a，那么b与c必须要定位双向双指针，在a+b<=c时，b调大或c调小都可以，会有歧义，但是a+b>c时，没有可以调整的指针使得当前状态改变。定b也是这样分析。

所以要定c

如果此时a+b>c那么如果a增大已经为a+b>c，所以此时只要a小于b都可以构成三角形，

这时一共有b-a个数。

如果a+b<=c，那么就需要调整b，使得找到a+b>c的情况在进行上面操作。

代码实现

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int n = nums.size();int ret = 0;for (int c = n - 1; c >= 2; c--) {int a = 0, b = c - 1;while (b > a) {if (nums[a] + nums[b] > nums[c]) {ret += b - a;b--;} else {a++;}}}return ret;}
};

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

题目意思解释

题目描述很详细，并且也没有需要注意的，那么这就不解释了。

算法原理

这一道题应该算是所有题中最好写的，甚至比力扣第一题还简单好多。

这就不在多说了。

只给一点提示：需要用的双指针类型为双向双指针。

需要注意的是，自己熟悉一下本题的返回形式，还有注意保证函数在所有情况下都要有返回值，在没有找到的情况下，力扣一般是返回负数的。

代码实现

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {sort(price.begin(),price.end());int n=price.size();int r=n-1,l=0;while(r>l){if(price[r]+price[l]>target){r--;}else if(price[r]+price[l]<target){l++;}else{return {price[l],price[r]};}}return {-1,-1};}
};

题目七：15. 三数之和 - 力扣（LeetCode）

题目意思解释

同样这道题理解起来很容易，但是需要注意的一点就是：[nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，并且这个三元组还不能重复，比如测试用例的一，其中构成0的三元组中有两个[-1,0,1]，但是只算一个。

算法原理

其实算法实现思路还是与构成三角形的那个一样还是定一，然后剩余两个用双向双指针法。如果是自己能完全不参考任何代码可以写出，那么这一题完全不是问题。

注意：

一定要符合题中的要求，三元组不可以重复，一定要保证每一个三元组不同，那么需要注意的就是两次的first或者second或者third不可以相同，需要去重。

代码实现

代码实现给两个版本，一个是for循环，一个是while循环

while

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;int n=nums.size();sort(nums.begin(),nums.end());for(int first=0;first<n;first++){   if(nums[first]>0) break; //小优化  如果first大于0 ，first又为最小，那么无论如何都构不成0if (first>0 && nums[first] == nums[first - 1])// 去重{continue;}int third=n-1;int second=first+1;int target = -nums[first];while(second<third){if(nums[second]+nums[third]>target){third--;}else if(nums[second]+nums[third]<target){second++;}else{ret.push_back({nums[first],nums[second],nums[third]});second++,third--;while(second<third && nums[second]==nums[second-1]) second++;// 去重while(second<third && nums[third]==nums[third+1]) third--;// 去重}}}return ret;}
};

for

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;int n=nums.size();sort(nums.begin(),nums.end());for(int first=0;first<n;first++){   if (first>0 && nums[first] == nums[first - 1]){continue;}int third=n-1;int target = -nums[first];for(int second=first+1;second<n;second++){if(second>first+1 && nums[second]==nums[second-1]){continue;}while( third>second&& nums[second]+nums[third]>target){third--;}if(second>=third) break;if (nums[second] + nums[third] == target){ret.push_back({nums[first],nums[second],nums[third]});}}}return ret;}
};

题目八：18. 四数之和 - 力扣（LeetCode）

题目意思解释

意思与上一题完全一致

算法原理

同样为双指针，但是需要定二，另外两个为双向双指针。其实这道题就是在外壳套一个三数之和。

很简单。

代码实现

代码实现给两个版本，一个是for循环，一个是while循环

while

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 first = 0; first < n; first++){if (first > 0 && nums[first] == nums[first - 1]){continue;}for (int second = first + 1; second < n; second++){if (second > first+1 && nums[second] == nums[second - 1]){continue;}int fourth = n - 1;int third=second+1;long long ans = (long long)target - nums[first] - nums[second];while(third<fourth){if (nums[third] + nums[fourth] > ans){fourth--;}else if(nums[third] + nums[fourth] < ans){third++;}else{ret.push_back({ nums[first],nums[second],nums[third],nums[fourth] });third++,fourth--;while(third<fourth && nums[third]==nums[third-1]) third++;while(third<fourth && nums[fourth]==nums[fourth+1]) fourth--;}}}}return ret;}
};

for

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 first = 0; first < n; first++){if (first > 0 && nums[first] == nums[first - 1]){continue;}for (int second = first + 1; second < n; second++){if (second > first+1 && nums[second] == nums[second - 1]){continue;}int fourth = n - 1;long long ans = (long long)target - nums[first] - nums[second];for (int third = second + 1; third < n; third++){if (third > second + 1 && nums[third] == nums[third - 1]){continue;}while (fourth > third && nums[third] + nums[fourth] > ans){fourth--;}if (third >= fourth) break;if (nums[third] + nums[fourth] == ans){ret.push_back({ nums[first],nums[second],nums[third],nums[fourth] });}}}}return ret;}
};

到这里就结束了，

那么为了检测，可以去力扣上搜一些双指针的题去练习

977.有序数组的平方

题目链接：. - 力扣（LeetCode）

189.轮转数组

题目链接：. - 力扣（LeetCode）

167.两数之和 II - 输入有序数组

题目链接：. - 力扣（LeetCode）

344.反转字符串

题目链接：. - 力扣（LeetCode）

557.反转字符串中的单词 III

题目链接：. - 力扣（LeetCode）

557.反转字符串中的单词 III

题目链接：. - 力扣（LeetCode）

19.删除链表的倒数第 N 个结点

题目链接：. - 力扣（LeetCode）