给定一个包含 n 个整数的数组 nums
和一个目标值 target
,判断 nums
中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target
相等?找出所有满足条件且不重复的四元组。
注意:
答案中不可以包含重复的四元组。
示例:
给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。 满足要求的四元组集合为: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
题目标签:Array / Hash Table / Two Pointers
题目链接:LeetCode / LeetCode中国
Language | Runtime | Memory |
---|---|---|
cpp | 32 ms | 2 MB |
class Solution {
public:
vector<vector<int>> twoSum(vector<int>& nums, int target, int st, int ed) {
vector<vector<int> > res;
while (st < ed) {
if (nums[st] + nums[ed] == target) {
if (res.empty() || res.back()[0] != nums[st]) {
res.push_back(vector<int>{nums[st], nums[ed]});
}
++st;
--ed;
} else if (nums[st] + nums[ed] > target) {
--ed;
} else {
++st;
}
}
return res;
}
vector<vector<int>> nSum(vector<int>& nums, int target, int st, int ed, int n) {
vector<vector<int> > res;
if (n == 2) {
return twoSum(nums, target, st, ed);
} else {
for (int i=st; i<=ed; ++i) {
int num = nums[i];
if (res.empty() || res.back()[0] != num) {
auto ret = nSum(nums, target-num, i+1, nums.size()-1, n-1);
for (auto r : ret) {
vector<int> tmp;
tmp.push_back(num);
tmp.insert(tmp.end(), r.begin(), r.end());
res.push_back(tmp);
}
}
}
return res;
}
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
return nSum(nums, target, 0, nums.size()-1, 4);
}
};