14、★★ 四个数组分组-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

来源：力扣（LeetCode）

思路：完全没有思路：

四个数组，如果遍历就是 N的四次方的复杂度！可以进行折半，复杂度就折半变成了 n的²

答案思路

1）将其中两个分别相加，得出全部可能的值！重要的思想，当然也可以将其中3组相加，n的三次方的时间复杂度！

2）然后再用哈希判断，需要记录合适的结果的 出现次数！

3）getOrDefault()方法，是map中的方法！如果有就得到value值，没有就设置默认值！

代码：

1）分组 + 哈希：看了答案思路自己写的

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //套循环肯定不行
        //只用记录元组个数

        //最重要的是，将四个数组拆分成两两一组，变成了上一题的 两数之和！
        int n = nums1.length;
        int num = 0;
        Map map = new HashMap<>();
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                int sum = nums1[i] + nums2[j];
                if(map.containsKey(sum)) map.put(sum,map.get(sum) + 1);
                else map.put(sum,1);
            }
        }

        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                int sum = nums3[i] + nums4[j];
                if(map.containsKey(0 - sum)){
                    num = num + map.get(0 - sum);
                }
            }
        }
        return num;
    }
}

2）优化了一个 方法

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //套循环肯定不行
        //只用记录元组个数

        //最重要的是，将四个数组拆分成两两一组，变成了上一题的 两数之和！
        int n = nums1.length;
        int num = 0;
        Map map = new HashMap<>();
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                int sum = nums1[i] + nums2[j];
                map.put(sum,map.getOrDefault(sum,0) + 1);
            }
        }

        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                int sum = nums3[i] + nums4[j];
                if(map.containsKey(0 - sum)){
                    num += map.get(0 - sum);
                }
            }
        }
        return num;
    }
}

3)使用Map效果很差！因为空间大，计算耗时！

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        //记录杂志字符串出现的次数
        Map map = new HashMap<>();
        for (int i = 0; i < magazine.length(); i++) {
            char c = magazine.charAt(i);
            map.put(c,map.getOrDefault(c,0) + 1);
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            char c = ransomNote.charAt(i);
            if(!map.containsKey(c)) return false;
            map.put(c,map.get(c) - 1);
            if(map.get(c) < 0) return false;
        }
        return true;
    }
}