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

“双指针”算法下篇

news 来源：原创 2024/9/19 13:57:26

对双指针这一思想在OJ 里面的相关应用，感兴趣的友友们，可以看下此篇博客

双指针算法（上篇）

一·盛最多水的容器

1·题目链接：盛最多水的容器

2· 分析

1）解法一：暴力求解

就是逐一进行判断，找出乘积相乘最大的：比如说第一个元素与第二个元素进行结合得出 1* 1 = 1

第一个元素与第三个元素进行结合得出 1*2 = 2……经过一轮的循环，最终得出这一轮乘积最大的

是1*8 = 8

接下来进行第二轮的循环：第二个元素与第三个元素结合，与第四个元素结合……

最终经过几轮循环得出最大乘积：49，即为所求。

对应时间复杂度O（N^2）

但是这并不是一个优解的算法

2）解法二：双指针

这个双指针代表的意义：表示一个范围：所有边界位置的一个范围

3· 算法原理

1）先假设当前左右指针所在位置对应的得出的体积是 V

2）比较此时 left 和 right 所对应的元素大小，让指向元素小的指针进行移动

3）此时left ，right 指向的位置可以再次得出一个体积，与之前所得出的 V 进行比较，取最大者即

可，重复上述过程，直至left ，right 指针相遇

4）注意细节处理：计算体积之前，需要先求出 2指针所指向元素最小的是哪一个

4· OJ代码

class Solution {
public:int maxArea(vector<int>& height) {int n = height.size();int left = 0,right = n-1;int v = 0;while(left < right){int ret = min(height[left],height[right]) * (right-left);v = max(v,ret);//代码核心// 找高度最小的if(height[left] > height[right] )right--;else++left;}return v;}
};

二·找出和为 s 的两个数

1·题目链接两数之和

2· 分析

解法一：暴力枚举

对于这个思想，想必各位都不陌生吧，直接2个 for 循环，判断nums[left] + num[right] 是否为

target 即可

时间复杂度：O（N^2）

解法二：双指针

针对暴力枚举，我们还可以进行优化：

定义2个指针：left ，right

3· 算法原理

1) 排序（注意：不要直接对原始数组进行变动）

2）指针移动

初始化：left = 0,right = n-1(n: 数组大小）

num[left] + num[right] > target ,right --: 因为此时是一个有序的数组，num[left] <= num[right] 一定

是成立的，当num[left] + num[right] > target 的时候就需要缩小数据范围，进行左移

num[left] + num[right] < target ,left++: 同理，一个有序的数组，num[left] + num[right] < target ,

此时就需要增大数据，右移

num[left] + num[right] = target ：记录此时的元素数值

3）把当前 num[left] num[right] 进行保存一下

4）遍历原始数组，找到指定元素之后，返回对应的元素下标

注意此时不能一次性就把 num[left] num[right]遍历完

4· OJ代码

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> ret;vector<int> tmp(nums.begin(),nums.end());int f1 = 0,f2 = 0;//1.排序sort(tmp.begin(),tmp.end());//2. 双指针int left = 0;int right = nums.size()-1;while(left < right){if(tmp[left]+ tmp[right] > target)--right;else if(tmp[left]+ tmp[right] == target){f1 = tmp[left];f2 = tmp[right];break;}else++left;}for(int i = 0;i<nums.size();i++){if(nums[i] == f1){ret.push_back(i);break;}}for(int i = 0;i<nums.size();i++){if(i != ret[0] && nums[i] == f2){ret.push_back(i);break;}}return ret;}
};

三·有效的三角形个数

1·题目链接有效的三角形个数

2· 分析

构成三角形的条件：

任意的两边之和都大于第三边或者是任意的两边之差都小于第三边

解法一：暴力枚举

三层循环，假设第一次对应数为 a , b ,c

只需要判断 a+b > c,a+c > b, b+c > c 这三个条件是否同时满足即可。

对应时间复杂度：O(N^3)

解法二：双指针

假设此时固定一个最大的数，只需要在最大的数左区间里面找出两个数 a+b > 最大的数即可

不知道看到这，各位是否已经有了思路？

此时问题就已经简化成了：找两数之和大于 S 的问题

这不就是上面找出两数之和为S 的一个变形嘛。

3· 算法原理

我们知道 a<= b <= c ,一定满足 a+ b > c 这个条件，此时，a,b ,c 这个组合移动可以构成有

效的三角形。

1）先进行排序

2）从右向左依次固定一个最大的数

3）指针移动

当 num[left] + num[right ] > c , 此时就是对应的 right - left j就是这一轮匹配到的个数，同时right

指针向左移动

因为此时数组是有序的，num[right ] 必定是大于或者等于 num[left ] ，right 向左移动是缩小

num[left] + num[right ] 的范围

num[left] +num[right ] <= c,left 指针向右移动：此时 num[left] 小于或者等于 num[right] ，需要找

下一个匹配的组合，只能left ++

草图分析：

4· OJ代码

class Solution {
public:int triangleNumber(vector<int>& nums) {//排序sort(nums.begin(),nums.end());int ret = 0;int n  = nums.size();//依次固定最大的数for(int max_i = n-1;max_i >= 2 ;--max_i){int left = 0,right = max_i-1;//注意更新依次max_i，左右指针都要进行改变，所有不能定义在外面while(left < right){if(nums[left] +nums[right]> nums[max_i]){ret += right-left;right--;}else // <= max_i ,对当前指向的数据扩大++left;}}return ret;}
};

四· 三数之和

1. 题目链接三数之和

2. 分析

解法一：暴力枚举

3个 for 循环，依次判断所得之是否为0 即可

对应的伪代码

    for (int i = 0; i < n - 2; ++i){for (int j = i + 1; j < n - 1; ++j){for (int k = j + 1; k < n; ++k){if(num[i]+num[j]+num[k] == 0)}}}

细节处理：题目要求三元组不能重复

时间复杂度：O (N^3)

前面我们做过两数之和，其实此题就是上面的变形

解法二：双指针结合单调性

3. 算法原理

为了下面描述方便：假设这三个数分别对应 a, b ,c

1) 排序

2）先固定一个数 a , 接下来只需要在数a 的右边区间找到 b + c = target - a 的两个数

3）指针移动

当 num[left] + num[right] > target -a ,right -- :依然是借助单调性

注意right 再向左移动的过程中，可能会遇到重复的数据，需要进行去重的处理

当 num[left] + num[right] < target-a ,left++:

注意left 再向y右移动的过程中，可能会遇到重复的数据，需要进行去重的处理

当 num[left] + num[right] == target-a ，此时把对应的数据放到一个变量里面，继续进行查找

4）当left right，相遇的时候，就对a 进行更新，依然注意去重的处理

4. OJ代码

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;int  n = nums.size();//1. 排序sort(nums.begin(),nums.end());// 2. 双指针结合单调性for(int i = 0; i < n-2 && nums[i] <= 0;){int left = i+1,right = n-1;while(left < right){if(nums[left] + nums[right] == -nums[i]){ret.push_back({nums[i],nums[left],nums[right]});--right;//去重while(left < right && nums[right] == nums[right+1] ){--right;}}else if (nums[left] + nums[right] < -nums[i]){++left;//去重while(left < right && nums[left] == nums[left-1]){++left;}}else  // (nums[left] + nums[right] > -nums[i]){--right;//去重while(left < right && nums[right] == nums[right+1] ){--right;}   }}++i;//去重while(i < n-2 && nums[i] == nums[i-1]){++i;}}return ret;}
};

五· 四数之和

1. 题目链接四数之和

2. 分析

想必各位看到这里，应该自认为小case ，这不就是轻松拿捏嘛。双指针走起

解法一：暴力枚举

解法二：双指针结合单调性

这里分析的思路和上面的找三数之和是一样滴

3. 算法原理

1）排序

2）依次固定 2个数，借助循环

3）指针移动

4）去重问题

这里不仅仅涉及到left ，right 去重，还有在固定2个数的时候也需要去重

5）注意数据的溢出

在我们提交代码的时候发现一下报错：

此报错的意思：有符号数据的溢出问题

解决：

此时只需把int 改为long 即可

4. OJ代码

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 n1 = 0;n1 < n-3; ){//依次枚举第二个数for(int n2 = n1+1;n2 < n-2 ; ){//双指针+单调性  //注意溢出问题//超出int范围long add =(long) target-(long)nums[n1]-(long)nums[n2];// int add = target-nums[n1]-nums[n2];int left = n2+1,right = n-1;while(left < right){if(nums[left] + nums[right] ==add ){ret.push_back({nums[n1],nums[n2],nums[left],nums[right]});--right;//去重while(left < right && nums[right] == nums[right+1]){--right;}}else if(nums[left] + nums[right]  > add ){--right;//去重while(left < right && nums[right] == nums[right+1]){--right;}}else  // (nums[left] + nums[right] < add ){++left;while(left < right && nums[left] == nums[left-1]){++left;}}}++n2;//去重while(n2 < n-2  && nums[n2] == nums[n2-1]){++n2;}}//去重++ n1;while(n1 < n-3 && nums[n1] == nums[n1-1]){++n1;}}return ret;}
};