四数相加Ⅱ 力扣454

一、题目

给你四个整数数组 nums1 、 nums2 、 nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

二、思路

这题直接想法就是四个for循环，count统计符合条件的情况，但时间复杂度到了四次方，超时了。

如何降低时间复杂度呢？ 可不可以分组处理？这样时间复杂度就会降低了。

可以用map两两分组存储，每组的和作为key，次数作为value，然后遍历nums3和nums4，判断-(nums3[k] + nums4[l])是否存在于map中，如果存在，则次数加1。

这样时间复杂度就降低到了二次方啦。

三、代码

关于map.getOrDefault() 和map.get()方法的一些解释：

map.get(sum)： 如果 sum 这个键不存在于 map 中，get 方法会返回 null。如果你直接对 null 进行加法操作（例如 null + 1），这会导致 NullPointerException。

map.getOrDefault(sum, 0)： 如果 sum 这个键不存在于 map 中，getOrDefault 方法会返回你指定的默认值 0，这样可以确保后续的加法操作是安全的，不会抛出异常。 因此，使用 getOrDefault(sum, 0) 是为了确保即使 sum 这个键不存在，也能正确地进行计数操作，而不会因为 null 值导致程序崩溃。

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int count = 0;
        Map<Integer,Integer> map = new HashMap<>();
 //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for(int i = 0; i < nums1.length;i++) {
            for(int j = 0;j<nums2.length;j++) {
                int sum = nums1[i] + nums2[j];
                map.put(sum,map.getOrDefault(sum,0) + 1);
            }
        }
 //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
         for (int i : nums3) {
            for (int j : nums4) {
                count = count + map.getOrDefault(-(i+j),0);
            }
        }
        return count;
     }
}