https://leetcode.cn/problems/4sum/
题目描述
给你一个由n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组
思路
类似于之前的两数之和三数之和, 排序+双指针即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| typedef std::vector<std::vector<int>> array2d;
class Solution {
public:
array2d fourSum(std::vector<int>& nums, int target) {
if (nums.size() < 4)
return {};
std::sort(nums.begin(), nums.end());
size_t len = nums.size();
array2d result;
for (size_t i = 0; i < len - 3; ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)
break;
if ((long)nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target)
continue;
for (size_t j = i + 1; j < len - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1])
continue;
if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)
break;
if ((long)nums[i] + nums[j] + nums[len - 1] + nums[len - 2] < target)
continue;
size_t left = j + 1, righ = len - 1;
while (left < righ) {
auto sum = (long)nums[i] + nums[j] + nums[left] + nums[righ];
if (sum == target) {
result.push_back({ nums[i], nums[j], nums[left], nums[righ] });
while (left < righ && nums[left] == nums[left + 1])
++left;
++left;
while (left < righ && nums[righ] == nums[righ - 1])
--righ;
--righ;
}
else if (sum < target)
++left;
else
--righ;
}
}
}
return result;
}
};
|
