Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
61 lines (51 sloc) 1.62 KB
/*
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in 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]
]
*/
/*
Hints:
just same idea as 015 3Sum
One more fixed number
*/
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> answer;
int len = nums.size();
sort(nums.begin(), nums.end());
for(int i=0;i<len-3;i++){
if(i!=0 && nums[i]==nums[i-1]) continue;
for(int j=i+1;j<len-2;j++){
if(j!=i+1 && nums[j]==nums[j-1]) continue;
int l = j+1;
int r = len-1;
int sum = 0;
while(l<r){
sum = nums[i] + nums[j] + nums[l] + nums[r];
if(sum == target){
vector<int> tmp(4,0);
tmp[0] = nums[i];
tmp[1] = nums[j];
tmp[2] = nums[l];
tmp[3] = nums[r];
answer.push_back(tmp);
while(l<r && nums[l]==tmp[2]) ++l;
while(l<r && nums[r]==tmp[3]) --r;
}
else if(sum > target) --r;
else if(sum < target) ++l;
}
}
}
return answer;
}
};