//问题：找数组中和为0的三元组
//方法：排序后，扫描数组，转化为2sum问题
//2sum对应一个循环，3sum对应两重循环，4sum对应三重循环
//O(n^2)
#include <algorithm>
class Solution
{
public:
vector<vector<int>> threeSum(vector<int>& a)
{
vector<vector<int>> res;
int n = a.size();
if(n<3) return res;
sort(a.begin(), a.end()); //排序
//扫描a[i],后面在用left和right首尾两指针扫描
for(int i = 0; i<n && a[i]<=0; i++) //第一个数只能是负数或0，加此判断以节省时间，如果不加次判断，则i<n-2即可
{
int target = -a[i]; //将第一个数的相反数定为2sum的target
int left = i+1; //i=0~n-3
int right = n-1;
while(left < right) //用两个指针分别从a[i+1]和整个数组末尾开始向中间扫描 ,找到所有可以满足和为-a[i]的数对
{
int sum = a[left] + a[right];
if(sum < target) left++; //仅移动前面指针
else if(sum > target) right--; //仅移动后面指针
else //满足3sum要求
{
res.push_back({a[i], a[left], a[right]}); //将满足的三元组push到结果向量中(也可以用vector<int>{a[i], a[left], a[right]})
while(left<right && a[left+1] == a[left]) left++; //以免第二个数重复
while(left<right && a[right-1] == a[right]) right--;//以免第三个数重复
left++; //前后指针都移动，下一次判断
right--;
}
}
while(i+1 < n && a[i+1] == a[i]) i++; //以免第一个数重复
}
return res;
}
};
/*注：
也可用set避免重复
set<vector<int>> res;
...
vector<vector<int>>(res.begin(), res.end());//用迭代器将set转为vector
*/
/*
问题：找与目标值相等的4个数
三重循环即可
用set可避免重复结果
*/
class Solution
{
public:
vector<vector<int>> fourSum(vector<int> &nums, int target)
{
if(nums.size() < 4) return vector<vector<int>>(); //或者用{{}}
set<vector<int>> res;
sort(nums.begin(), nums.end());
//扫描a[i],a[j]后面接left,right两个指针
for (int i = 0; i < int(nums.size() - 3); i++)
{
for (int j = i + 1; j < int(nums.size() - 2); j++)
{
// if (j > i + 1 && nums[j] == nums[j - 1]) continue; //遇到重复数时不执行下面语句，如果用set可以不进行此判断
int left = j + 1, right = nums.size() - 1; //i=0~n-4,j=i+1~n-3
while (left < right)
{
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target)
{
vector<int> out{nums[i], nums[j], nums[left], nums[right]};
res.insert(out); //用set,当有重复结果时，插入会失败
left++; right--;
}
else if (sum < target) left++;
else right--;
}
}
}
return vector<vector<int>>(res.begin(), res.end()); //由set转化为vector输出
}
};
