[LeetCode][18. 四数之和] 4种方法：暴力，双指针，DFS，HashMap
By Long Luo
方法一：暴力枚举
思路与算法：
和 15. 三数之和 类似，我们先对数组进行排序，然后 \(4\) 层循环即可。
由于结果肯定会出现重复的数字，所以我们使用 \(\texttt{Set}\) 来去重，代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public List<List<Integer>> fourSum(int[] nums, int target) {
if (nums == null || nums.length < 4) {
return new ArrayList<>();
}
Arrays.sort(nums);
int n = nums.length;
Set<List<Integer>> ans = new HashSet<>();
for (int first = 0; first < n - 3; first++) {
for (int second = first + 1; second < n - 2; second++) {
for (int third = second + 1; third < n - 1; third++) {
for (int fourth = third + 1; fourth < n; fourth++) {
if (nums[first] + nums[second] + nums[third] + nums[fourth] == target) {
ans.add(Arrays.asList(nums[first], nums[second], nums[third], nums[fourth]));
}
}
}
}
}
return new ArrayList<>(ans);
}
我们可以在每次循环中增加判断，防止出现重复四元组，使用 \(\texttt{List}\)：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
51
52
53
54
55
56
57
58
59
60
61
62public List<List<Integer>> fourSum(int[] nums, int target) {
if (nums == null || nums.length < 4) {
return new ArrayList<>();
}
Arrays.sort(nums);
int len = nums.length;
List<List<Integer>> ans = new ArrayList<>();
for (int 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 - 3] + nums[len - 2] + nums[len - 1] < target ) {
continue;
}
for (int 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 - 2] + nums[len - 1] < target) {
continue;
}
for (int k = j + 1; k < len - 1; k++) {
if (k > j + 1 && nums[k] == nums[k - 1]) {
continue;
}
if ((long)nums[i] + nums[j] + nums[k] + nums[k + 1] > target) {
break;
}
if ((long)nums[i] + nums[j] + nums[k] + nums[len - 1] < target) {
continue;
}
for (int l = k + 1; l < len; l++) {
if (l > k + 1 && nums[l] == nums[l - 1]) {
continue;
}
if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
ans.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
}
}
}
}
}
return ans;
}
复杂度分析：
- 时间复杂度：\(O(n^4)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(logn)\)， 空间复杂度主要取决于排序额外使用的空间 \(O(logn)\)。