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

【优选算法之双指针】No.2--- 经典双指针算法(下)

news 2024/11/16 6:48:36

文章目录

前言
一、双指针示例：
- 1.1 ⽔果成篮
- 1.2 和为s的两个数字
- 1.3 三数之和
- 1.4 四数之和
二、双指针总结：

前言

在这里插入图片描述

👧个人主页：@小沈YO.
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：优选算法
🔑本章内容：双指针
记得评论📝 +点赞👍 +收藏😽 +关注💞哦~

提示：以下是本篇文章正文内容，下面案例可供参考

一、双指针示例：

1.1 ⽔果成篮

题⽬链接：611. 有效三⻆形的个数
题⽬描述：
解法⼀（暴⼒求解）（会超时）：
算法思路：三层 for 循环枚举出所有的三元组，并且判断是否能构成三⻆形。
虽然说是暴⼒求解，但是还是想优化⼀下：
判断三⻆形的优化：

如果能构成三⻆形，需要满⾜任意两边之和要⼤于第三边。但是实际上只需让较⼩的两条边之和⼤于第三边即可。
因此我们可以先将原数组排序，然后从⼩到⼤枚举三元组，⼀⽅⾯省去枚举的数量，另⼀⽅⾯⽅便判断是否能构成三⻆形

解法⼆（排序 + 双指针）：
算法思路：先将数组排序。
根据「解法⼀」中的优化思想，我们可以固定⼀个「最⻓边」，然后在⽐这条边⼩的有序数组中找出⼀个⼆元组，使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的，我们可以利⽤「对撞指针」来优化。
设最⻓边枚举到 i 位置，区间 [left, right] 是 i 位置左边的区间（也就是⽐它⼩的区间）：
◦ 如果 nums[left] + nums[right] > nums[i] ：
▪ 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐ nums[i] ⼤的⼆元组
▪ 满⾜条件的有 right - left 种
▪ 此时 right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进⼊下⼀轮判断
◦ 如果 nums[left] + nums[right] <= nums[i] ：
▪ 说明 left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满⾜条件的⼆元组
▪ left 位置的元素可以舍去， left++ 进⼊下轮循环
C++代码（数组模拟哈希/容器）

class Solution {
public:int triangleNumber(vector<int>& nums) {int cnt=0;sort(nums.begin(),nums.end());if(nums.size()<3)return 0;for(int i=nums.size()-1;i>=2;i--){int left=0,right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){cnt+=right-left;right--;}else{left++;}}}return cnt;}
};

1.2 和为s的两个数字

题⽬链接：剑指 Offer 57. 和为s的两个数字
题⽬描述：
解法⼀（暴⼒解法，会超时）：
算法思路：两层 for 循环列出所有两个数字的组合，判断是否等于⽬标值。
算法流程：
两层 for 循环：
◦ 外层 for 循环依次枚举第⼀个数 a ；
◦ 内层 for 循环依次枚举第⼆个数 b ，让它与 a 匹配；
ps ：这⾥有个魔⻤细节：我们挑选第⼆个数的时候，可以不从第⼀个数开始选，因为 a 前⾯的数我们都已经在之前考虑过了；因此，我们可以从 a 往后的数开始列举。
◦ 然后将挑选的两个数相加，判断是否符合⽬标值
解法⼆（双指针 - 对撞指针）：
算法思路：
注意到本题是升序的数组，因此可以⽤「对撞指针」优化时间复杂度。算法流程（附带算法分析，为什么可以使⽤对撞指针）：
a. 初始化 left ， right 分别指向数组的左右两端（这⾥不是我们理解的指针，⽽是数组的下标）
b. 当 left < right 的时候，⼀直循环
i. 当 array[left] + array[right] == sum时，说明找到结果，记录结果，并且返回；
ii. 当 array[left] + array[right] < sum时：
• 对于 array[left] ⽽⾔，此时 array[right] 相当于是 array[left] 能碰到的最⼤值（别忘了，这⾥是升序数组哈~）。如果此时不符合要求，说明在这个数组⾥⾯，没有别的数符合 nums[left] 的要求了（最⼤的数都满⾜不了你，你已经没救了）。因此，我们可以⼤胆舍去这个数，让 left++ ，去⽐较下⼀组数据；
• 那对于 array[right] ⽽⾔，由于此时两数之和是⼩于⽬标值的， array[right] 还可以选择⽐ array[left] ⼤的值继续努⼒达到⽬标值，因此 right 指针我们按兵不动；
iii. 当 array[left] + array[right] > sum时，同理我们可以舍去 array[right] （最⼩的数都满⾜不了你，你也没救了）。让 right-- ，继续⽐较下⼀组数据，⽽ left 指针不变（因为他还是可以去匹配⽐ array[right] 更⼩的数的）
C++代码

class Solution {
public:vector<int> FindNumbersWithSum(vector<int> array,int sum) {sort(array.begin(),array.end());vector<int> v;int left=0,right=array.size()-1;while(left<right){if(array[left]+array[right]<sum)left++;else if(array[left]+array[right]>sum)right--;else{v.push_back(array[left]);v.push_back(array[right]);break;}}return v;}
};

1.3 三数之和

题⽬链接：15. 三数之和
题⽬描述：
解法（排序+双指针）：
算法思路：本题与两数之和类似，是⾮常经典的⾯试题
与两数之和稍微不同的是，题⽬中要求找到所有「不重复」的三元组。那我们可以利⽤在两数之和那⾥⽤的双指针思想，来对我们的暴⼒枚举做优化：
i. 先排序；
ii. 然后固定⼀个数 a ：
iii. 在这个数后⾯的区间内，使⽤「双指针算法」快速找到两个数之和等于 -a 即可。
但是要注意的是，这道题⾥⾯需要有「去重」操作~
i. 找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；
ii. 当使⽤完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素
C++代码

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> vv;sort(nums.begin(),nums.end());set<vector<int>> sv;for(int i=nums.size()-1;i>=2;){int left=0,right=i-1;while(left<right){if(nums[left]+nums[right]<(-nums[i])){left++;}else if(nums[left]+nums[right]>(-nums[i])){right--;}else{vv.push_back({nums[left],nums[right],nums[i]});left++;right--;while(left<right&&nums[left]==nums[left-1])left++;while(left<right&&nums[right]==nums[right+1])right--;}}i--;while(i>=2&&nums[i]==nums[i+1])i--;}return vv;}
};

1.4 四数之和

题⽬链接：18. 四数之和
题⽬描述：
解法（排序 + 双指针）
算法思路：
a. 依次固定⼀个数 a ；
b. 在这个数 a 的后⾯区间上，利⽤「三数之和」找到三个数，使这三个数的和等于 target- a 即可。
C++代码

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> vv;if(nums.size()<4)return vv;sort(nums.begin(),nums.end());for(int dest=nums.size()-1,cur=dest-1;dest>=3;){while(cur>=2){int left=0,right=cur-1;while(left<right){long long sum=nums[left]+nums[right];long long tmp=(long long)target-nums[dest]-nums[cur];if(sum<tmp){left++;}else if(sum>tmp){right--;}else{vv.push_back({nums[left],nums[right],nums[cur],nums[dest]});left++;right--;while(left<right&&nums[right]==nums[right+1])right--;while(left<right&&nums[left]==nums[left-1])left++;}}cur--;while(cur>=2&&nums[cur]==nums[cur+1])cur--;}dest--;while(dest>=3&&nums[dest]==nums[dest+1])dest--;cur=dest-1;}return vv;}
};