题目描述
Given an array nums
of n integers and an integer target
, are there elements a, b, c, and din nums
such that a + b + c + d = target
? Find all unique quadruplets in the array which gives the sum of target
.
Note:
The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
解题思路
【C++解法】
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
if(nums.size()<4) return res;
sort(nums.begin(),nums.end());
if(nums[0]+nums[1]+nums[2]+nums[3]>target ||
nums[nums.size()-4]+nums[nums.size()-3]+nums[nums.size()-2]+nums[nums.size()-1]<target) return res;
for(int i=0;i<nums.size()-3;i++){
auto target3 = target-nums[i];
if(nums[i+1]+nums[i+2]+nums[i+3]>target3) break;
if(nums[nums.size()-3]+nums[nums.size()-2]+nums[nums.size()-1] < target3) continue;
for(int j = i+1; j<nums.size()-2;j++){
auto target2 = target3-nums[j];
if(nums[j+1]+nums[j+2]>target2) break;
if(nums[nums.size()-2]+nums[nums.size()-1]<target2) continue;
int front = j+1, back = nums.size()-1;
while(front<back) {
auto sum2 = nums[front]+nums[back];
if(sum2<target2) front++;
else if(sum2>target2) back--;
else {
res.push_back({nums[i],nums[j],nums[front++],nums[back--]});
while(front<back && nums[front-1]==nums[front]) front++;
while(front<back && nums[back+1]==nums[back]) back--;
}
}
while(j<nums.size()-2 && nums[j]==nums[j+1]) j++;
}
while(i<nums.size()-3 && nums[i]==nums[i+1]) i++;
}
return res;
}
};