《算法闯关指南：优选算法-双指针》--07三数之和，08四数之和
《算法闯关指南：优选算法-双指针》--07三数之和，08四数之和
🔥草莓熊Lotso：个人主页
❄️个人专栏：《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受。
🎬博主简介：
前言：
聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。 递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。 贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题 内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。
07.三数之和
题目链接：
题目描述：
题目示例：
解法：（排序+双指针）
--暴力算法就不讲了，（排序+暴力+set去重）。时间复杂度过高，肯定过不了。
算法思路：
本题与两数之和为s类似，是非常经典的面试题。
与两数之和稍微不同的是，题目中要求找到所有【不重复】的三元组。那我们可以利用在两数之和为s那里的双指针思想，来对我们暴力枚举进行优化：
- 先排序
- 然后固定一个数a；
- 在这个数后面的区间内，使用【双指针算法】快速找到两个数之和等于 -a 即可。
但是我们需要注意的是，这道题里面需要有【去重】操作！
找到一个结果之后，不要停，left++，right-- 缩小区间后， left 和 right 指针也要【跳过重复】的元素；
当使用完一次双指针算法之后，固定的 a 也要 【跳过重复】的元素。
C++代码演示：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
//排序
sort(nums.begin(),nums.end());
int n=nums.size();
for(int i=0;i<n;)//固定数a(nums[i]),这里i先不++，后面会处理
{
int left=i+1,right=n-1,target=-nums[i];
if(nums[i]>0) break;
while(left<right)
{
int sum=nums[left]+nums[right];
if(sum<target) left++;
else if(sum>target) right--;
else {
ret.push_back({nums[i],nums[left],nums[right]});
left++,right--;
//去重一
while(left<right&&nums[left]==nums[left-1]) left++;
while(left<right&&nums[right]==nums[right+1]) right--;
}
}
//去重二
i++;//这里i++;
while(i<n&&nums[i]==nums[i-1]) i++;
}
return ret;
}
};算法总结&&笔记展示：
笔记字有点丑，大家见谅：
08.四数之和
题目链接：
题目描述：
题目示例：
解法：（排序+双指针）
--暴力解法这里还是不提了，肯定超时。
算法思路：
- 依次固定一个数 a；
- 在这个数 a 的后面区间上，利用【三数之和】找到三个数，使这三个数的和等于 target-a 即可。
C++代码演示：
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 i=0;i<n;)//固定数a
{
for(int j=i+1;j<n;)//固定数b
{
int left=j+1,right=n-1;long long targetsub=(long long)target-nums[i]-nums[j];
//这里注意数据大小
while(left<right)
{
long long sum=nums[left]+nums[right];
if(sum<targetsub) left++;
else if(sum>targetsub) right--;
else{
ret.push_back({nums[i],nums[j],nums[left],nums[right]});
left++;
right--;
//去重一
while(left<right&&nums[left]==nums[left-1]) left++;
while(left<right&&nums[right]==nums[right+1]) right--;
}
}
//去重二
j++;
while(j<n&&nums[j]==nums[j-1]) j++;
}
//去重三
i++;
while(i<n&&nums[i]==nums[i-1]) i++;
}
return ret;
}
};算法总结&&笔记展示：
笔记字有点丑，大家见谅：
往期回顾：
《算法闯关指南：优选算法-双指针》--01移动零，02复写零
《算法闯关指南：优选算法-双指针》--03快乐数，04盛水最多的容器
《算法闯关指南：优选算法-双指针》--05有效三角形的个数，06查找总价值为目标值的两个商品
结语：本篇博客介绍了LeetCode中三数之和与四数之和问题的解题思路。通过排序+双指针算法优化暴力解法，重点讲解了去重操作的实现方法。对于三数之和，固定一个数后用双指针在剩余区间寻找两数之和；四数之和则通过固定两个数后转化为三数之和问题。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。
✨把这些内容吃透超牛的！放松下吧✨ ʕ˘ᴥ˘ʔ づきらど
腾讯云开发者
