LeetCode：454. 四数相加 II —— 哈希表为什么叫哈希表~

这篇具有很好参考价值的文章主要介绍了LeetCode：454. 四数相加 II —— 哈希表为什么叫哈希表~。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🍎道阻且长，行则将至。🍓

🌻算法，不如说它是一种思考方式🍀

算法专栏： 👉🏻123

hash是什么，哈希表为什么叫哈希表？
LeetCode：454. 四数相加 II —— 哈希表为什么叫哈希表~

一、🌱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
来源：力扣（LeetCode）
难度：中等
提示：
n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28
示例 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

🌴解题

哈希表

4个数组如果使用暴力解法就需要4层for循环，那时间复杂度将是O(n⁴)。
所以和上一题LeetCode：1. 两数之和类似，本题还是可以使用哈希表。我们可以把四个数组分为两个组，分别对每个组求和（时间复杂度O(n²) ），将第一组求和结果加入到map的key中，value就是出现的次数。第二组就用于寻找map中是否有相反数，最后统计次数返回。

code：

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if(!map.containsKey(nums1[i]+nums2[j])){
                    map.put(nums1[i]+nums2[j],1);
                }else{
                    map.put(nums1[i]+nums2[j],map.get(nums1[i]+nums2[j])+1 );
                }
            }
        }
        int ans=0;

        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                if(map.containsKey(-(nums3[i]+nums4[j]))){
                    ans+=map.get(-(nums3[i]+nums4[j]));
                }
            }
        }

        return ans;
    }
}