内容简介：本题的思路和3Sum一致，无非是多加一层循环。当然，时间复杂度就为O(n^3)了。时间复杂度：O(n^3)空间复杂度：O(n)
原题
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一致，无非是多加一层循环。当然，时间复杂度就为O(n^3)了。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector< vector<int> > rs;
sort(nums.begin(), nums.end());
int l = nums.size(), f = 0, b = 0;
for (int i = 0; i < l - 3; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < l - 2; j++) {
f = j + 1;
b = l - 1;
if (j - i > 1 && nums[j] == nums[j - 1]) continue;
while (f < b) {
if (nums[i] + nums[j] + nums[f] + nums[b] < target) {
while (nums[f] == nums[++f]) {}
} else if(nums[i] + nums[j] + nums[f] + nums[b] > target) {
while (nums[b] == nums[--b]) {}
} else {
vector<int> tmp = {nums[i], nums[j], nums[f], nums[b]};
rs.push_back(tmp);
while (nums[f] == nums[++f]) {}
while (nums[b] == nums[--b]) {}
}
}
}
}
return rs;
}
};
时间复杂度：O(n^3)
空间复杂度：O(n)
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Algorithms Unlocked
Thomas H. Cormen / The MIT Press / 2013-3-1 / USD 25.00
Have you ever wondered how your GPS can find the fastest way to your destination, selecting one route from seemingly countless possibilities in mere seconds? How your credit card account number is pro......一起来看看 《Algorithms Unlocked》 这本书的介绍吧!
