【优选算法必刷100题】第007~008题（双指针算法）：三数之和、四数之和问题求解
🔥艾莉丝努力练剑：个人主页
❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶
⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平
🎬艾莉丝的算法专栏简介：
目录
007 三数之和
力扣链接：15. 三数之和
力扣题解链接：排序+双指针解决【三数之和】
题目描述：
1.1 题目解析
1.2 思路1：暴力
解法一：暴力求解（会超时）——
时间复杂度：O(n^3)，空间复杂度：O(logn)。
1.3 思路2：排序 + 双指针
1.3.1 算法思路
本题与两数之和类似，是非常经典的面试题。与两数之和稍微不同的是，题目中要求找到所有【不重复】的三元组。那我们可以利用在两数之和那里用的双指针思想，来对我们的暴力枚举做优化：
1、先排序；
2、然后固定一个数a：
3、在这个数后面的区间内，使用「双指针算法」快速找到两个数之和等于a即可。
但是要注意的是，这道题里面需要有【去重】操作——
1、找到一个结果之后，left和[right指针要【跳过重复】的元素；
2、当使用完一次双指针算法之后，固定的a也要【跳过重复】的元素。
1.3.2 代码实现
代码演示：
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; //1、排序 sort(nums.begin(),nums.end()); //2、固定 int n = nums.size(); for(int i = 0;i < n;) { int left = i + 1,right = n - 1,target = -(nums[i]); while(left < right) { //a <= 0 if(nums[i] > 0)break; int sum = nums[left] + nums[right]; if(sum > target)right--; else if(sum < target)left++; else{ ret.push_back({nums[i],nums[left],nums[right]}); left++; right--; //继续缩小区间 //left、right查重 while(left < right && nums[left] == nums[left - 1])left++; while(left < right && nums[right] == nums[right + 1])right--; } } //i查重 //i在这里移动，不在for循环 i++; while(i < n && nums[i] == nums[i - 1])i++; } return ret; } };时间复杂度：O(n^3)，空间复杂度：O(logn)。
1.4 过程推算
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下！
1.5 反思
总结：
1、没学到STL，vector<vector<int>> ret;和ret.push_back({nums[i],nums[left],nums[right]});这步根本想不到，直接来刷题了，对自己的实力没有清晰的认知（QAQ）；
2、没想到固定的值a <= 0，这个常数级别的小优化想不到；
3、还是去重操作，都在一个条件判断下去重了，left和right在while(left < right)里面去重，i应该在它外面去重，因为刚才我已经让for循环的i++（i移动）这个操作搬到for里面来进行了，这样去重了，这样移动完之后，得到的i就是下一步我要固定的那个数了；
4、i移动的操作在while循环里面搞定，for循环for(int i = 0;i < n;)这个可以空着不写没有想到；
5、时间复杂度：O(n^2)，for循环嵌套一个while循环；
6、空间复杂度：无限接近于O(logn)——只是在排序那里稍微占了点空间，压栈会占用logn的空间，其他都是只用了有限个变量。
008 四数之和
力扣链接：18. 四数之和
力扣题解链接：排序+双指针解决【四数之和】问题
题目描述：
2.1 题目解析
如下所示——
2.2 思路1：暴力
解法一：暴力求解（会超时）——
大家直接去看上面的【三数之和】：
2.3 思路2：排序 + 双指针
2.3.1 算法思路
1、依次固定一个数a；
2、在这个数a的后面区间上，利用【三数之和】找到三个数，使这三个数的和等于target - a即可，这里注意有两个区间，大的区间里面固定一个数b，小的区间里面定义一个left和right两个下标指针，里面的两数之和，加上a和b，加起来和target比。
2.3.2 代码实现
代码演示——
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { // 创建数组，存放返回值 vector<vector<int>> ret; // 1、排序 sort(nums.begin(), nums.end()); // 2、固定i int n = nums.size(); for (int i = 0; i < n;) { // 固定j for (int j = i + 1; j < n;) { // 3、双指针 int left = j + 1, right = n - 1; while (left < right) { // // a >= 0 // if (nums[i] > 0) // break; // // b >= 0 // if (nums[j] > 0) // break; long sum = nums[left] + nums[right]; long tmp = nums[i] + nums[j]; if (sum > (target - tmp)) right--; else if (sum < (target - tmp)) left++; else { ret.push_back( {nums[i], nums[j], nums[left], nums[right]}); left++; right--; // left、right去重 while (left < right && nums[left] == nums[left - 1]) left++; while (left < right && nums[right] == nums[right + 1]) right--; } } // j查重，j移动 j++; while (j < n && nums[j] == nums[j - 1]) j++; } // i查重，i移动 i++; while (i < n && nums[i] == nums[i - 1]) i++; } return ret; } };时间复杂度：O(n^3)，空间复杂度：O(logn)。
2.4 过程推算
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下！
2.5 反思
1、整体做下来思路正确、逻辑没问题，这一点值得肯定（这里出的岔子就是在a <= 0，b <= 0的判断加上，就报错了）；
2、没有自己独立地想到int类型遇到超级大的数据会怎么样，这里要在定义变量的时候把类型改成long，或者直接临时强制类型转换；
3、吸取了vector<vrctor<int>> ret;和ret.push_back({...});的教训，可以的！
结尾
往期回顾：
【优选算法必刷100题】第005~006题（双指针算法）：有效三角形的个数、查找总价格为目标值的两个商品问题求解
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡
૮₍ ˶ ˊ ᴥ ˋ˶₎ა
