《算法闯关指南：优选算法-双指针》--07三数之和，08四数之和
🔥草莓熊Lotso：个人主页
❄️个人专栏：《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受。
🎬博主简介：
目录
前言：
聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。 递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。 贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题 内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。
07.三数之和
题目链接：
15. 三数之和 - 力扣（LeetCode）
题目描述：
题目示例：
解法：（排序+双指针）
--暴力算法就不讲了，（排序+暴力+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.四数之和
题目链接：
18. 四数之和 - 力扣（LeetCode）
题目描述：
题目示例：
解法：（排序+双指针）
--暴力解法这里还是不提了，肯定超时。
算法思路：
- 依次固定一个数 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中三数之和与四数之和问题的解题思路。通过排序+双指针算法优化暴力解法，重点讲解了去重操作的实现方法。对于三数之和，固定一个数后用双指针在剩余区间寻找两数之和；四数之和则通过固定两个数后转化为三数之和问题。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。
✨把这些内容吃透超牛的！放松下吧✨
ʕ˘ᴥ˘ʔ
づきらど
