18. 四数之和
难度中等1502
给你一个由 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：
代码语言：javascript复制输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2：
代码语言：javascript复制输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]提示：
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
解题思路：排序 双指针
这道题其实就是 15. 三数之和 的拓展，本质上还是一样的，只不过剪枝和去重的细节又多了一点！
首先一开始还是排序，这个问题我们已经在三数之和那道题中说过了，具体的可以去翻阅笔记查看！
接着就是遍历 nums，因为这次是四个数，双指针分别占了两个，所以我们在最外层的循环还需要套两层，比三数之和多了一层循环，最重要的是多了一层循环，也就是多了一个剪枝和去重工作！但是大体步骤和三数之和是类似的！
1、先来讲讲最外层这个 i 的剪枝和去重工作：
这道题三数之和不太一样，这道题要求四个数的和不能超过 target，那么我们在最外层的剪枝判断中能不能说直接 nums[i] > target 就剪枝呢？肯定是不行的，因为 target 可能是负数，并且 nums[i] 以及 nums[i] 后面的数也可能是负数，这个时候一个数加上负数，它们的和反而是会变小的，所以 不能直接判断是否 nums[i] > target 就剪枝！举个例子，比如 {-4, -1, 0, 0} 数组中我们要找的是和为 -5 的，那么这个数组刚刚好就是一个解，但是如果我们如果直接判断 nums[i] > target 也就是 -4 > -5 后剪枝，那么就错过了这个解，那么就错了！
所以最外层的剪枝工作是需要修改一下的，我们还需要判断 nums[i] 是否大于等于0，因为我们的数组是排序过的，这样子就能避免 nums[i] 后面加的数是负数，所以正确的剪枝判断是： if(nums[i] > target && nums[i] >= 0) break;
接下来就是最外层的去重操作，这个和三数之和是一模一样的，只要判断 nums[i] 与 nums[i - 1] 是否相同，是的话就说明重复了，直接 continue，除此之外 还需要注意边界问题就是需要让 i > 0 防止 nums[i -1] 索引越界！具体的原因可以参考三数之和的笔记！
2、接下来讲一下第二层 j 的剪枝和去重工作：
首先 j 肯定是通过最外层的 i 1 来开始遍历的，所以对于去重工作，都是类似的，只是这里不是 nums[j] > 0，而是 nums[j] > i 1 来进行防止索引越界，并且只要 nums[j] == nums[j - 1] 我们就直接 continue 即可！
对于第二层的剪枝，不只是单单的判断 nums[j] > target 就剪枝，因为有可能我们最外层的 nums[i] 就是一个负数，而 nums[i] nums[j] 之后得到的数比 target 还小，那么这就不能剪枝了，所以我们要考虑到最外层的情况！
正确的剪枝操作：if(nums[i] nums[j] > target && nums[i] >= 0 && nums[j] >= 0) continue;
上述剪枝操作也可以进行一下化简：if(nums[i] nums[j] > target && nums[i] >= 0) continue;
这个化简就是简单的数学问题了，要求 nums[i] >= 0，因为数组的有序的，所以 nums[j] 肯定也是 >= 0 的，所以就没必要判断 j了！
3、最后说一下双指针的移动
这个大概操作和三数之和是一样的！但是有一些细节问题，就是直接是三个数与 target 比较，现在要变成四个数！
除此之外，我们四个数相加，对于这道题的数据来说是会发生溢出的，所以我们在相加的时候需要将它们的类型转化为 long 类型以上才行，而对于类型转化表达式，我们只需要对其中一个变量进行类型转化，其它的三个变量会根据不同类型进行隐式类型转化的，也就是一个类型是 long，其它类型是 int 的话，最后相加的结果还是 long！这样子就不会溢出了！
其它问题就和三数之和是一样的！
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end()); // 别忘了排序！
vector<vector<int>> vv;
int n = nums.size();
for(int i = 0; i < nums.size(); i)
{
// 进行一级剪枝和一级去重
// 剪枝中注意如果target是负数的话且nums[i]>target，那么直接不能剪枝
// 因为虽然nums[i]>target，但是nums[i]加上nums[j]不一定比target大，所以要排除nums[i]小于0的情况！
if(nums[i] > target && nums[i] >= 0)
break;
if(i > 0 && nums[i] == nums[i - 1])
continue;
for(int j = i 1; j < nums.size(); j)
{
// 进行二级剪枝和二级去重
// 注意这里剪枝的时候不只是判断nums[j]>target，因为有可能nums[i]是负数，这样子它们两个数相加之后可能会比target小
// 这里写成if(nums[i] nums[j] > target && nums[i] >= 0) 也是可以的，数学问题！
if(nums[i] nums[j] > target && nums[i] nums[j] >= 0)
break;
// 去重时候如果前一个是i的话，那么相当于j是i这一轮的第一遍执行，所以不需要continue
if(j > i 1 && nums[j] == nums[j - 1])
continue;
int left = j 1, right = n - 1;
while(left < right)
{
// 四个数加起来可能会溢出，所以要先变成long类型
if((long) nums[i] nums[j] nums[left] nums[right] > target)
right--;
else if((long) nums[i] nums[j] nums[left] nums[right] < target)
left ;
else
{
vv.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
// left和right的去重
while(left < right && nums[right] == nums[right - 1])
right--;
while(left < right && nums[left] == nums[left 1])
left ;
// 别忘了再更新一次left和right才是不重复的那个值
left ;
right--;
}
}
}
}
return vv;
}
};
