05 August 2008
给定四个长度为 n 的整数数组 nums1、nums2、nums3 和 nums4，返回元组 (i, j, k, l) 的数量，使得：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
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
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<>();
int sum1 = 0;
int count = 0;
for(int i = 0; i < nums1.length; i++) {
for(int j = 0; j < nums2.length; j++) {
sum1 = nums1[i] + nums2[j];
if(map.containsKey(sum1)) {
int num = map.get(sum1);
map.put(sum1, ++num);
} else {
map.put(sum1, 1);
}
}
}
for(int i = 0; i < nums3.length; i++) {
for(int j = 0; j < nums4.length; j++) {
int temp = 0 - nums3[i]- nums4[j];
if(map.containsKey(temp)) {
count += map.get(temp);
}
}
}
return count;
}
}
two hashmaps
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
HashMap<Integer, Integer> map1 = new HashMap<>();
HashMap<Integer, Integer> map2 = new HashMap<>();
for(int i = 0; i < nums1.length; ++i){
for(int j = 0; j < nums1.length; ++j){
map1.put(nums1[i] + nums2[j], map1.getOrDefault(nums1[i] + nums2[j], 0) + 1);
map2.put(nums3[i] + nums4[j], map2.getOrDefault(nums3[i] + nums4[j], 0) + 1);
}
}
int res = 0;
for(int key : map1.keySet()){
if(map2.containsKey(-key)){
res += map1.get(key) * map2.get(-key);
}
}
return res;
}
}