【优选算法之双指针】No.2--- 经典双指针算法(下)
文章目录
- 前言
- 一、双指针示例：
- 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;
}
};
二、双指针总结：
- 1.移动零：快排的思想：数组划分区间 - 数组分两块
- 2.复写零：从后往前(涉及到覆盖的)
- 3.快乐数：快慢指针(设计循环)
- 4.盛水最多的容器：对撞指针
- 5.有效三角的个数：固定一边+对撞指针
- 6.和为S的两个数字：排序+对撞指针
- 7.三数之和：排序+对撞指针+固定
- 8.四数之和：排序+对撞指针(三指针)+固定