四数之和

四数之和

思路分析

此题是从四个数组中寻找相加为0的四个数，其中会有重复出现可能，所以可以使用 Map 哈希法来解决。

key 存放前两个数组a+b的值，value存储a+b出现的次数。

先遍历前两个数组，存储a+b的值和出现的次数。

再遍历剩下两个数组，寻找 0-c-d 是否在map中出现，使 res加上 出现的次数，即可获得答案。

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> map = new HashMap<>();
        // 寻找 a+b
        for(int a : nums1){
            for(int b : nums2){
                int sum = a+b;
                map.put(sum, map.getOrDefault(sum,0)+1);
            }
        }
        //寻找 0-c-d
        int cnt = 0;
        for(int c : nums3){
            for(int d : nums4){
                cnt += map.getOrDefault(0-c-d,0);
            }
        }

        return cnt;
    }
}