【LeetCode刷题】三数之和、四数之和

本文主要是介绍【LeetCode刷题】三数之和、四数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目1：LCR 7.三数之和

思路分析：

结合昨天的两数之和等与目标值，这道题的算法很简单了，所以这里重点讲一下一个关键细节要求：去重。

1. 容器set去重，将数据导入set去重。
2. 重，就是三个数都相同，当两个数字都相同，若要满足题意，则第三个数一定相同。根据这点我们在代码过程中体现

思路1：排序+暴力枚举+set去重

思路2：单调性+双指针+细节处理去重

1. 排序；
2. 固定一个最小元素；
3. 双指针查找；

代码实现：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 1.排序--升序sort(nums.begin(), nums.end());int n = nums.size();vector<vector<int>> vv; // 处理非单值返回// 2.固定一个最小元素for (int i = 0; i < n - 2;) {// 小优化：最小的数都大于0，后面就不存在了if (nums[i] > 0)return vv;// 3.双指针查找int left = i + 1, right = n - 1, target = -nums[i];while (left < right) {int sum = nums[left] + nums[right];if (sum == target) {vv.push_back({nums[i], nums[left], nums[right]});// 去重（1） left++, right--;while (left < right && nums[left] == nums[left - 1])left++;while (left < right && nums[right] == nums[right + 1])right--;} else if (sum > target)right--;elseleft++;}// 去重（2）i++;while (i < n - 2 && nums[i] == nums[i - 1])i++;}return vv;}
};

代码注释：
去重（1）：找到一个答案后，在固定一个数的情况下继续寻找，只要再出现一个数和已得到的答案数组相同，则若要符合题意，第三个数一定相同。所以我们只需要防止在固定一个数的情况下，再出现一个数相同的情况。
去重（2）固定这个最小数结束后，下一个数如果相同，也会出现重复，所以也需要跳过与上一个数相同的元素。

LeetCode链接：LCR 7.三数之和

题目2：18.四数之和

思路分析：

和上面三个数求和一样，只是代码量的增加，很锻炼代码能力，思路和处理方式没有区别。
需要值得注意的是一个报错：类型溢出。

思路1：排序+暴力枚举+set去重

思路2：单调性+双指针+细节去重

代码实现：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {// 1.排序--升序sort(nums.begin(), nums.end());int n = nums.size();vector<vector<int>> vv; // 处理非单值返回// 2.固定一个最小元素for (int j = 0; j < n - 3;) {for (int i = j + 1; i < n - 2;) {// 3.双指针查找int left = i + 1, right = n - 1;long long target1 = target - nums[j];long long target2 = target1 - nums[i];while (left < right) {int sum = nums[left] + nums[right];if (sum == target2) {vv.push_back({nums[j], nums[i], nums[left], nums[right]});// 去重（1）left++, right--;while (left < right && nums[left] == nums[left - 1])left++;while (left < right && nums[right] == nums[right + 1])right--;} else if (sum > target2)right--;elseleft++;}// 去重（2）i++;while (i < n - 2 && nums[i] == nums[i - 1])i++;}// 去重（3）j++;while (j < n - 3 && nums[j] == nums[j - 1])j++;}return vv;}
};

LeetCode链接：18.四数之和

这篇关于【LeetCode刷题】三数之和、四数之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---