题意
从数组中找出满足和为target
的四元组。
思路
- 想法1:暴力,(O(n^4))。
- 想法2:排序 指针。思路类似前面的三数之和,只不过这里的指针多了一个,后两个指针相遇时第二个指针后移一个单位。时间复杂度:(O(n^3)),空间复杂度:(O(1))。
代码
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int len = nums.size();
if(len < 4) return {};
int L, R;
vector<vector<int> > res;
sort(nums.begin(), nums.end());
for(int i = 0; i < len; i)
{
if(i && nums[i - 1] == nums[i]) continue;
for(int j = i 1; j < len; j)
{
if(j > i 1 & nums[j] == nums[j - 1]) continue;
L = j 1;
R = len - 1;
while(L < R)
{
int sum = nums[i] nums[j] nums[L] nums[R];
if(sum < target)
L;
else if(sum > target)
--R;
else
{
res.push_back({nums[i], nums[j], nums[L], nums[R]});
while(L 1 < len && nums[L 1] == nums[L]) L;
while(R - 1 > 0 && nums[R - 1] == nums[R]) --R;
L; --R;
}
}
}
}
return res;
}
};
总结
排序 指针!