题目
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]
]
思路
本题思路很简单,有了前面3Sum的基础,这里只要将 target-d,然后就是3Sum的解题方法。
C++
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int> > result;
if(nums.size() < 4)
return result;
sort(nums.begin(),nums.end());
int pMid = 0;
int pEnd = 0;
for(int i = 0;i<nums.size() - 3; i++){
//转化成3Sum问题
int subTarget=target - nums[i];
if(i > 0 && nums[i] == nums[i-1])
continue;
for(int j = i + 1;j<nums.size()-2;j++){
int subTarget2 = subTarget - nums[j];
pMid = j + 1;
pEnd = nums.size() - 1;
if(j > i + 1 && nums[j] == nums[j-1])
continue;
while(pMid < pEnd){
int sum1 = nums[pMid] + nums[pEnd];
if(sum1 < subTarget2){
pMid ++;
}
else if(sum1 > subTarget2){
pEnd --;
}
else{
vector<int> tempVec(4,0);
tempVec[0] = nums[i];
tempVec[1] = nums[j];
tempVec[2] = nums[pMid];
tempVec[3] = nums[pEnd];
result.push_back(tempVec);
while(pMid < pEnd && nums[pMid] == nums[pMid+1]) //去除重复元素
pMid ++;
while(pMid < pEnd && nums[pEnd] == nums[pEnd -1])
pEnd --;
pMid ++;
pEnd --;
}
}
}
}
return result;
}