目录
1. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0题解
- 这道题我们根据它的用例来分析，要找下标不同的数，使其相加和为0。
- 下面虽然有三组解，下标也不同，但是第一组和第三组它们的数是相同的，因此只能去重留下一组。
算法原理：
- 一般这里我们还是首先会想到暴力求解，这是没问题的，因为我们的优化就是从暴力求解上来的。
- 对于这道题，它要最后把结果还要去重，我们一般考虑得到结果然后每个排序之后在去重。其实我们可以先排序。然后在去重，去重我们有容器set和unordered_set，因此第一种解法出来了。
解法一：排序+暴力枚举+利用set去重
解法二：排序之后，使用单调性，使用双指针算法解决问题
本题是找三元组，因此我们排好序之后，固定一个数，然后利用双指针求解。所以以后遇到三元组的问题可以采用这种方法
- 排序
- 固定一个数a（优化：a<=0）
- 在该数后面的区间内，利用 “双指针算法” 快速找到两个的和等于-a即可
本题需要去重，有两种思路，本题实现用第二种实现
- 容器set
- 算法去重
去重：同时要 避免越界
- 找到⼀个结果之后，left和right指针要「跳过重复」的元素
- 当使⽤完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素
不漏组合：
- 并非一轮找到一个组合就可以了，可能一轮中可以找到多个组合
- 找到一种结果后，不要停，缩小区间，继续寻找 ++left,--right
代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
// 排序
sort(nums.begin(), nums.end());
int a = 0, n = nums.size();
vector<vector<int>> ret;
while (a < n) {
// 如果当前数字大于0，则三数之和一定大于0，直接结束循环
if (nums[a] > 0) break;
int left = a + 1, right = n - 1;
while (left < right) {
int sum = nums[a] + nums[left] + nums[right];
if (sum < 0) {
++left;
} else if (sum > 0) {
--right;
} else {
//❌ret.push_back({a,left,right})
// 找到一组解
ret.push_back({nums[a], nums[left], nums[right]});
// 优雅的去重 left right
//下一位 和当前位相等，就++跳过，直到不等
while (left < right && nums[left] == nums[++left]);
while (left < right && nums[right] == nums[--right]);
}
}
// 跳过重复元素
while (a + 1 < n && nums[a] == nums[a + 1]) a++;
a++;
}
return ret;
}
};批注：
2.四数之和
题目链接：18.四数之和
题目描述：
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]题解
这道题和上面三数之和几乎一模一样
算法原理:
解法一：排序+暴力枚举+容器set去重
时间复杂度O(N^4)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end()); // 先排序
int n = nums.size();
set<vector<int>> uniqueResults; // 使用 set 去重
// 四重循环暴力枚举
for (int a = 0; a < n - 3; a++) {
for (int b = a + 1; b < n - 2; b++) {
for (int c = b + 1; c < n - 1; c++) {
for (int d = c + 1; d < n; d++) {
long long sum = (long long)nums[a] + nums[b] + nums[c] + nums[d];
if (sum == target) {
uniqueResults.insert({nums[a], nums[b], nums[c], nums[d]});
}
}
}
}
}
// 转换 set 结果为 vector<vector<int>>
return vector<vector<int>>(uniqueResults.begin(), uniqueResults.end());
}set转化为vector
解法二：排序+双指针
- 依次固定一个数 a
- 在 a 后面的区间内，利用 “三数之和” 找到三个数，是这三个数字的和等于 target - a 即可
三数之和
- 依次固定一个数 b
- 在 b 后面的区间内，利用 “双指针” 找到两个数，使这两个数的和等于 target - a - b 即可
处理细节问题：
- 去重
- 不漏
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
//排序
sort(nums.begin(),nums.end());
int a=0,b=1,n=nums.size();
vector<vector<int>> ret;
while(a<n-3)
{
int b=a+1;
while(b<n-2)
{
//直接采取 sum=a+b+left+right 存在越界情况
//两两 拆分
long long target_=(long long)target-nums[a]-nums[b];
int left=b+1,right=n-1;
while(left<right)
{
long long sum=nums[left]+nums[right];
if(sum<target_)
left++;
else if(sum==target_)
{
ret.push_back({nums[a],nums[b],nums[left],nums[right]});
while(left<right && nums[left]==nums[++left]);
while(left<right && nums[right]==nums[--right]);
}
else
right--;
}
//相同 就跳过
//直到 不同再跳出
while(b<n-2 && nums[b]==nums[++b]);
}
while(a<n-3 && nums[a]==nums[++a]);
}
return ret;
}
};报错：
这里要 采取 long long ，两两拆分 ，防止越界 （可 详见 代码注释）