【LeetCode刷题日记】454：四数相加Ⅱ

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言经过前面的学习我们已经知道了哈希表的三种实现方式的选择后面我们继续学习哈希表的相关算法题学会融会贯通增强对哈希表的理解能力。题目背景LeetCode454给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) 使得 A[i] B[j] C[k] D[l] 0。为了使问题简单化所有的 A, B, C, D 具有相同的长度 N且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间最终结果不会超过 2^31 - 1 。例如:输入:A [ 1, 2]B [-2,-1]C [-1, 2]D [ 0, 2]输出:2解释:两个元组如下:(0, 0, 0, 1) - A[0] B[0] C[0] D[1] 1 (-2) (-1) 2 0(1, 1, 0, 0) - A[1] B[1] C[0] D[0] 2 (-1) (-1) 0 0题目答案class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { int res 0; MapInteger, Integer map new HashMapInteger, 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; } }题目解析关于这个题目最简单的思路就是用for循环进行多层的循环嵌套但是时间复杂度比较高因此我们的目的是把暴力四重循环 O(n4) 的时间复杂度优化到 O(n2)尽可能的把时间复杂度降低下面看具体的实现思路首先要明白我们要干什么nums1的一个数 nums2的一个数 nums3的一个数 nums4的一个数 0首先我们先把返回值搞清楚需要返回的是有几组所以我们直接定义int res0之后再进行修改。然后接下来我们的逻辑就是计算数组之间的和我们一开始想到的就是for循环进行四重遍历但时间复杂度太高因此我们在这里使用两个循环嵌套的方式降低的时间复杂度第一个循环的嵌套计算的前两个数组的所有和过程如下nums1 [A, B]nums2 [C, D]执行顺序是外层循环先拿A内层循环拿C→ AC内层循环拿D→ AD外层循环再拿B内层循环拿C→ BC内层循环拿D→ BD计算完sum之后我们需要创建一个Map集合来存放因为把 “前两个数的和” 当成 key把 “这个和出现了几次” 当成 value提前存好方便后面快速查找不用再重复计算。创建 map 就是为了用空间换时间把重复计算变成一次查找。大大减少了时间复杂度。相当于一个统计表后面我们要用到前面两个数组的和是直接进行查找。因此这里map.put(sum, map.getOrDefault(sum, 0) 1);的意思是我们把计算出来的sum看看它之前出现过几次没有就是 0这次又出现一次所以次数 1再把新次数存回去。接下来res map.getOrDefault(0 - i - j, 0);假设nums3 取的数2nums4 取的数3那么i j 5需要前两个数的和 0 - 5 -5去 map 里查-5出现了4 次→res 4→ 总数直接加 4,没有就返回0.因此最后直接返回res。结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励