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.
使用三重for循环，在最后一层使用哈希表，复杂度为O(n^3)，为了避免重复的解，使用set存储得到的vector
class Solution {
public:
vector<vector<int> > fourSum(vector<int>& nums, int target) {
int len = nums.size();
set<vector<int>> data;
unordered_map<int, int> data_map;
sort(nums.begin(), nums.end());
for(int i=0;i<len;i++){
data_map[nums[i]] = i;
}
for(int i = 0; i < len-3; i++){
for(int j=i+1; j<len-2; j++){
for(int k=j+1; k<len-1; k++)
{
int findNum = target - nums[i] - nums[j] - nums[k];
if(data_map.find(findNum) != data_map.end() && data_map[findNum] > k){
vector<int> temp = {nums[i], nums[j], nums[k], findNum};
data.insert(temp);
}
}
}
}
return vector<vector<int>>(data.begin(), data.end());
}
};
