四数之和
题目链接 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]]
题目解释
这个是选择四个元素,他们的和为target
算法原理
和三数之和一样的,我们是可以退化的.我们也是固定响应的元素.
代码编写
class Solution
{
public:
vector<vector<int>> fourSum(vector<int> &nums, int target)
{
vector<vector<int>> reuslt;
sort(nums.begin(), nums.end());
int i = nums.size() - 1;
while (i >= 3)
{
long long x = target - nums[i];
int j = i - 1;
while (j >= 2)
{
int left = 0;
int right = j - 1;
// 这里也是
long long y = x - nums[j];
while (left < right)
{
int sum = nums[left] + nums[right];
if (sum == y)
{
reuslt.push_back({nums[left], nums[right], nums[j], nums[i]});
left++;
right--;
while (left < right && nums[left] == nums[left - 1])
left++;
while (left < right && nums[right] == nums[right + 1])
right--;
}
else if (sum > y)
{
right--;
}
else
{
left++;
}
}
while (j >= 2 && (x - nums[j] == y))
{
--j;
}
}
while (i >= 3 && (target - nums[i] == x))
{
--i;
}
}
return reuslt;
}
};