算法——四数相加 二（leetcode454）

题目：

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

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

解析:这道题就是找到nums1和nums2、nums3、nums4不同元素之和为0的记录和，我看到这道题时首先是使用暴力解法去解决的但会被某些用例卡住超出时限，故暴力解法是不可行的其思想便是一遍遍遍历4个数组中的元素之和从0,0,0,0到n-1,n-1,n-1,n-1符合条件的便记录下来最后返回即可。

暴力解法（不可取）

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        // 记录满足条件元组个数
        int res = 0;
        // 四数之和
        int sum;
        int n = nums1.length;
        int i = 0, j = 0, k = 0, l = -1;
        while (i < n) {
            if (l < n) {
                l++;
            } else if (k < n) {
                l = 0;
                k++;
            } else if (j < n) {
                l = 0;
                k = 0;
                j++;
            } else {
                l = 0;
                k = 0;
                j = 0;
                i++;
            }
            if (i < n && j < n && k < n && l < n) {
                sum = nums1[i] + nums2[j] + nums3[k] + nums4[l];
                if (sum == 0)
                    res++;
            }
        }
        return res;
    }
}

优质解法（利用哈希法）

思路：

1、利用Map来存储nums1和nums2数组元素之和以及数组元素之和出现的次数前者为key后者为value

2、遍历nums3，nums4数组元素之和取相反数来索引上述Map的value累加至res变量中

3、返回res变量即可

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
      int res=0;
      Map<Integer,Integer> map=new HashMap();
      for(int i:nums1){
        for(int j:nums2){
            int sum=i+j;
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
      }
      for(int i:nums3){
        for(int j:nums4){
            res+=map.getOrDefault(-(i+j),0);
        }
      }
      return res;
    }
}

通过哈希法的学习掌握了Map的一个方法用法

map.getOrDefault(key,defaultValue)

我们可以通过调用上述方法来查找key若key存在则直接返回其对应value如果不存在则返回设置好的默认值