力扣-18.四数之和
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]]
四数之和与15. 三数之和解法类似，只是由一重循环变成了双重循环，剪枝和去重都多了一次。
一、三数之和求三数相加为0。解法：
对数组排序，然后固定第 i 个数，剪枝操作即当 第 i 个数指向都大于0了，那后面的无需再加一定大于0（数组已经由小到大排列好了），去重操作即当重复要跳过。但这里有一个问题，是判断 nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同。应该选择判断 nums[i] 与 nums[i-1] ，因为用另一种方法就把 三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。
当用左右指针分别指向 i +1 和 数组最后一位数。如果数字大于目标数，右指针减一，如果小于目标数，左指针加一。然后考虑左右指针去重问题，就是与后一个或者前一个数是否相等，相等就跳过的问题，很容易看代码理解不过多赘述了。
二、学了三数之和，四数之和也很好理解了。
其实就是在外多套用一层循环，对第一个数也做去重和剪枝。然后第二重循环和三数之和差不多。只是小细节需要注意。
我给出一些需要注意的地方：不能nums[i]>0 就返回值了，因为这里target可以是任意数，要将条件更正为 nums[i]>=0&&nums[i]>target 。
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; sort(nums.begin(),nums.end()); for(int i=0;i<nums.size();i++){ if(nums[i]>=0&&nums[i]>target){ break; } if(i>0&&nums[i]==nums[i-1])continue; for(int j=i+1;j<nums.size();j++){ if(nums[j]+nums[i]>=0&&nums[j]+nums[i]>target){ break; } if(j>i+1&&nums[j]==nums[j-1])continue; int left=j+1,right=nums.size()-1; while(right>left){ if((long)nums[i]+nums[j]+nums[right]+nums[left]>target){ right--; }else if((long)nums[i]+nums[j]+nums[right]+nums[left]<target){ left++; }else{ result.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]}); while(right>left&&nums[left]==nums[left+1])left++; while(right>left&&nums[right]==nums[right-1])right--; left++; right--; } } } } return result; } };