leetcode链接：
https://leetcode.cn/problems/4sum-ii/
分析
根据其数值大小的提示，不需要考虑数组越界的可能。
方法一：
暴力求解，其一定是可以做的，但是其时间复杂度为 n 的四次方，时间复杂度过高。
方法二：
初步引入哈希表，前三个数组循环，第四个数组放入到HashMap里面，判断其是否等于0。相较于方法一，时间复杂度有所下降，但是依然较高。
方法三： 看官方题解知
其将四个数相加分成了两个两个数相加，将数据对半分，然后将相加之后的相关结果放到HashMap中，然后判断两个map之间的数据。
方案一
初步引入哈希表，前三个数组循环，第四个数组放入到HashMap里面，判断其是否等于0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> nums4Hash = new HashMap<>();
int n = nums1.length, result = 0;
for (int i = 0; i < n; i++) {
nums4Hash.put(nums4[i], i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (nums4Hash.containsKey(-(nums1[i] + nums2[j] + nums3[k])))
result++;
}
}
}
return result;
}
}
|
结果
运行失败:
Time Limit Exceeded
运行超时，时间复杂度过高。
分析
时间复杂度：
O( n 的三次方 )
空间复杂度：
O( n )
方案二
方法三： 看官方题解知
其将四个数相加分成了两个两个数相加，将数据对半分，然后将相加之后的相关结果放到HashMap中，然后判断两个map之间的数据。
https://leetcode.cn/problems/4sum-ii/solution/si-shu-xiang-jia-ii-by-leetcode-solution/
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
| class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> nums12Hash = new HashMap<>(), nums34Hash = new HashMap<>();
int n = nums1.length;
final int[] result = { 0 };
int temp12 = 0;
int temp34 = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
temp12 = nums1[i] + nums2[j];
temp34 = -1 * (nums3[i] + nums4[j]);
if (nums12Hash.containsKey(temp12)) {
nums12Hash.replace(temp12, nums12Hash.get(temp12) + 1);
} else {
nums12Hash.put(temp12, 1);
}
if (nums34Hash.containsKey(temp34)) {
nums34Hash.replace(temp34, (nums34Hash.get(temp34) + 1));
} else {
nums34Hash.put(temp34, 1);
}
}
}
nums12Hash.forEach((k, v) -> {
if (nums34Hash.containsKey(k)) {
result[0] = result[0] + nums34Hash.get(k) * v;
}
});
return result[0];
}
}
|
结果
解答成功:
执行耗时:173 ms,击败了10.75% 的Java用户
内存消耗:42.8 MB,击败了11.38% 的Java用户
分析
时间复杂度：
O( n 的二次方 )
空间复杂度：
O( n 的二次方 )