【LeetCode】454. 四数相加 II

??今日学习的文章链接和视频链接

leetcode题目地址：454. 四数相加 II

?代码随想录题解地址：代码随想录

题目简介

给你四个整数数组?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. 暴力解法：把四个数组分成两个一组，共两组，求出他们每个元素排列组合的和，形成两个List(或者说ArrayList)，此处不用Set是因为，要容许重复的元素存在。//超出时间限制

// 超出时间限制
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    List<Integer> l1 = new ArrayList<>();
    List<Integer> l2 = new ArrayList<>();
    int len = nums1.length;
    for (int i = 0; i < len; i++){
        for (int j = 0; j < len; j++){
            l1.add(nums1[i] + nums2[j]);
        }
    }
    for (int i = 0; i < len; i++){
        for (int j = 0; j < len; j++){
            l2.add(nums3[i] + nums4[j]);
        }
    }
    int count = 0;
    for (int i : l1){
        for (int j : l2){
            if (i + j == 0) count++;
        }
    }
    return count;
}

实现过程中遇到哪些困难

无思路

看完代码随想录之后的想法

【解题思路】最暴力的解法：for循环四个数组，看看和是否为0（时间复杂度：O(n^4)）

思路和我的是一样的，不过我好像数据结构选错了，我用的List(ArrayList)，他用的Map(HashMap)，可以用Map的value值来存储元素重复出现的次数，就可以实现 “不去重” 的效果。

【想法】

1. 只能用Map，如果用List的话，无法计算重复的数据。例：

nums1?= [-1,-1]????????nums2?= [-1,1]????????nums3?= [-1,1]????????nums4?= [1,-1]

L1: [-2, 0, -2, 0]? ? ? ? L2:?[0, -2, 2, 0]

但输出：4????????????????预期结果：6

看完视频自己写的ACC：

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    Map<Integer, Integer> m1 = new HashMap<>();
    Map<Integer, Integer> m2 = new HashMap<>();
    int len = nums1.length;
    for (int i = 0; i < len; i++){
        for (int j = 0; j < len; j++){
            if (m1.containsKey(nums1[i] + nums2[j])){
                int temp = m1.get(nums1[i] + nums2[j]);
                m1.put(nums1[i] + nums2[j], ++temp);
            }else {
                m1.put(nums1[i] + nums2[j], 1);
            }
            
        }
    }
    for (int i = 0; i < len; i++){
        for (int j = 0; j < len; j++){
            if (m2.containsKey(nums3[i] + nums4[j])){
                int temp = m2.get(nums3[i] + nums4[j]);
                m2.put(nums3[i] + nums4[j], ++temp);
            }else {
                m2.put(nums3[i] + nums4[j], 1);
            }
            
        }
    }
    int count = 0;
    for (Map.Entry<Integer, Integer> entry : m1.entrySet()) {
        if (m2.containsKey(-entry.getKey())){
            count += entry.getValue() * m2.get(-entry.getKey());
        }
    }
    return count;
}

标准答案ACC：map.getOrDefault(sum, 0) 好妙啊！

getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。

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

学习时长

11：50?~ 12：50? 解题成功、看视频题解、写博客

---

今日收获

1. 多考虑Map键值对的特性，灵活地自定义其“值”代表的意义。

2. map.getOrDefault(a,b)

getOrDefault() 方法获取指定 key"a"?对应对 value，如果找不到 key ，则返回设置的默认值"b"。