每日快讯!力扣：18. 四数之和
18. 四数之和
给你一个由 n个整数组成的数组 nums，和一个目标值 target。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
(相关资料图)
0 <= a, b, c, d < n
a、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]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
第一种对法：
双指针法，时间复杂度O(n^3)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>>ans;
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]>target&&nums[j]+nums[i]>=0)break;
if(j>i+1&&nums[j]==nums[j-1])continue;
int left,right;
left = j+1,right=nums.size()-1;
while(left<right){
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{
ans.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
while(left<right&&nums[left]==nums[left+1])left++;
while(left<right&&nums[right]==nums[right-1])right--;
left++,right--;
}
}
}
}
return ans;
}
};
思路：沿用了三数之和的思路，在多加了一层循环，重点是去重和剪枝的细节
剪枝：
第一层剪枝：当nums[i]>target时若nums[i]大于或等于0就说明后面的数都是正数已经无法等于target
第二层剪枝：当nums[i]+nums[j]>target时同上
去重细节与三数之和相同
关键词：
