class Solution {
public:
/**
* @param numbers: Give an array numbersbers of n integer
* @param target: you need to find four elements that's sum of target
* @return: Find all unique quadruplets in the array which gives the sum of
* zero.
*/
vector<vector<int> > fourSum(vector<int> nums, int target) {
// write your code here
vector<vector<int>> ret;
set<int> dup;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); ++i) {
for (int j = i + 1; j < nums.size(); ++j) {
unordered_set<int> s;
for (int k = j + 1; k < nums.size(); ++k) {
int r = target - nums[i] - nums[j] - nums[k];
if (r < nums[j]) break;
if (r <= nums[k] && s.find(nums[k]) != s.end()) {
int h = hash(nums[i], nums[j], r, nums[k]);
if (dup.find(h) == dup.end()) {
vector<int> ans({nums[i], nums[j], r, nums[k]});
ret.push_back(ans);
dup.insert(h);
}
} else {
s.insert(r);
}
}
}
}
return ret;
}
int hash(int a, int b, int c, int d) {
return a + 10 * b + 100 * c + 35937 * d;
}
};
LintCode 58-四数之和
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
