《算法题讲解指南：优选算法-双指针》--07三数之和，08四数之和
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
07.三数之和
题目链接：
15. 三数之和 - 力扣（LeetCode）
题目描述：
题目示例：
解法：（排序+双指针）
算法思路：
本题与之前讲解的 两数之和为s 类似，是非常经典的面试题。
与两数之和稍微不同的是，题目中要求找到所有【不重复】的三元组。那我们可以利用在两数之和为s那里的双指针思想：
- 先排序
- 然后固定一个数 stub；
- 在这个数后面的区间内，使用【双指针算法】快速找到两个数之和等于 -stub即可。
但是我们需要注意的是，这道题里面需要有【去重】操作！
找到一个结果之后，不要停，left++，right-- 缩小区间后， left 和 right 指针也要【跳过重复】的元素；
当使用完一次双指针算法之后，固定的 stub 也要 【跳过重复】的元素。
C++代码演示：
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { //解法一：使用去重容器set(笔试可以直接秒题，但代码效率低) // sort(nums.begin(), nums.end()); // vector<vector<int>> vv; // set<vector<int>> s; // int stub = nums.size() - 1; // while(stub > 1 && nums[stub] >= 0) // { // int left = 0; // int right = stub - 1; // while(left < right) // { // if(nums[left] + nums[right] + nums[stub] > 0) // { // right--; // } // else if(nums[left] + nums[right] + nums[stub] < 0) // { // left++; // } // else{ // s.insert({nums[left], nums[right], nums[stub]}); // left++; // right--; // } // } // stub--; // } // for(auto e : s) // { // vv.push_back(e); // } // return vv; //解法二：不使用容器去重(针对面试，可以提升算法能力，而且代码效率高) sort(nums.begin(), nums.end()); vector<vector<int>> vv; int stub = nums.size() - 1; while(stub > 1 && nums[stub] >= 0) { int left = 0; int right = stub - 1; while(left < right) { if(nums[left] + nums[right] + nums[stub] > 0) { right--; } else if(nums[left] + nums[right] + nums[stub] < 0) { left++; } else{ vv.push_back({nums[left], nums[right], nums[stub]}); while(left < right && nums[left] == nums[left + 1]) { left++; } while(left < right && nums[right] == nums[right - 1]) { right--; } left++; right--; } } while(stub > 1 && nums[stub] == nums[stub - 1]) { stub--; } stub--; } return vv; } };算法总结及流程解析：
08.四数之和
题目链接：
18. 四数之和 - 力扣（LeetCode）
题目描述：
题目示例：
解法：（排序+双指针）
算法思路：
- 依次固定一个数 a；
- 在这个数 a 的后面区间上，利用【三数之和】找到三个数，使这三个数的和等于 target-a 即可。
C++代码演示：
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> vv; for(int i = 0; i < nums.size(); i++) { for(int j = i + 1; j < nums.size(); j++) { int left = j + 1; int right = nums.size() - 1; while(left < right) { long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right]; //哎给我整笑了，int溢出的例子是咋想出来的 if(sum > target) { right--; } else if(sum < target) { left++; } else{ vv.push_back({nums[i], nums[j], nums[left], nums[right]}); while(left < right && nums[left] == nums[left + 1]) { left++; } while(left < right && nums[right] == nums[right - 1]) { right--; } left++; right--; } } while(j < nums.size() - 1 && nums[j] == nums[j + 1]) { j++; } } while(i < nums.size() - 1 && nums[i] == nums[i + 1]) { i++; } } return vv; } };算法总结及流程解析：
结束语
到此，7三数之和、08四数之和 两道算法题就讲解完了。通过排序 + 双指针算法优化暴力解法，重点讲解了去重操作的实现方法。对于三数之和，固定一个数后用双指针在剩余区间寻找两数之和；四数之和则通过固定两个数后转化为三数之和问题。希望大家能有所收获！
