四数之和
题目链接 18. 四数之和
给你一个由
n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0a、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> fourSum(vector &nums, int target)
{
vector> 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 y)
{
right--;
}
else
{
left++;
}
}
while (j >= 2 && (x - nums[j] == y))
{
--j;
}
}
while (i >= 3 && (target - nums[i] == x))
{
--i;
}
}
r服务器托管网e服务器托管网turn reuslt;
}
};服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
