ACM 选手图解 LeetCode 四数相加Ⅱ

简介: 给定 4 个长度为 n 的整数数组,计算有多少个元组(i, j, k, l) 能满足:nums[i] + nums[j] + nums[k] + nums[l] == 0。

大家好呀,我是你们的帅蛋。


今天解决四数相加Ⅱ,这是目前打算的哈希实战系列的最后一道题。


坚持就是胜利,话不多说,直接开搞。

image.png

 LeetCode 454:四数相加Ⅱ



题意



给定 4 个长度为 n 的整数数组,计算有多少个元组(i, j, k, l) 能满足:


nums[i] + nums[j] + nums[k] + nums[l] == 0。



示例


输入: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


提示


  • 1 <= n <= 200
  • -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

题目解析


四数相加Ⅱ问题,难度中等。


这道题乍一看有点似曾相识,和我们上一道题【三数之和】有点差不多,但是架不住多看,一看原形毕露:因为实在是差的太多。


image.png

我在【三数之和】中写过,它的最优解是“排序 + 双指针”,强行用哈希解是为了练习哈希,为了不超时需要对各种细节的处理将难度拔高了一个 level,纯粹是吃饱了撑的自己搞自己。


本道题则是哈希解法的亲儿子,有 4 个独立的数组,只要找出 nums[i] + nums[j] + nums[k] + nums[l] = 0,同时题目也没要求找出不重复的四元组,这就不需要考虑去重,在难度上降了不少


这道题知道了用哈希还不够,还需要做一下小处理。


不知道大家还记不记得【两数之和】,遍历 nums 数组,对于当前元素 nums[i],查询哈希表中是否存在 target - nums[i]。


四数相加Ⅱ的解法可以将四数分为两组,即“分组 + 哈希”:


  • 初始化哈希表。
  • 分组:nums1 和 nums2 一组,nums3 和 nums4 一组。
  • 分别对 nums1 和 nums2 进行遍历,将所有 nums1 和 nums2 的值的和作为哈希表的 key,和的次数作为哈希表的 value。
  • 分别对 nums3 和 nums4 进行遍历,若 -(nums1[k] + nums4[l]) 在哈希表中,则四元组次数 +hash[-(nums3[k]+nums4[l])] 次。


图解


nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2] 为例。


首先初始化哈希表,key 存储 nums[i] + nums[j] 的所有元素和,value 存储对应出现的次数

image.png

# 初始化哈希表
hash = {}
cnt = 0

第一步,分别对 nums1 和 nums2 中的元素进行遍历,将所有 nums1 和 nums2 的值的和作为哈希表的 key,和的次数作为哈希表的 value。


nums1 的第 1 个元素为 1,nums2 的第 1 个元素为 -2,1 + (-2) = -1,-1 不在哈希表中,遂加入哈希表。

image.png


# 首先存储前两个数组之和
for n1 in nums1:
    for n2 in nums2:
        # 如果在哈希表中,则对应哈希值 +1
        if n1 + n2 in hash:
            hash[n1 + n2] += 1
        # 如果不在哈希表中,放入哈希表
        else:
            hash[n1 + n2] = 1

遍历完 nums1 和 nums2 所有元素,哈希表变为如下所示:


image.png

即 hash[-1] = 1,hash[0] = 2,hash[1] = 1。


第二步,分别对 nums3 和 nums4 进行遍历,若 -(nums1[k] + nums4[l]) 在哈希表中,则四元组次数 +hash[-(nums3[k]+nums4[l])] 次。


遍历 nums3 和 nums4 中所有元素,nums3 的第 1 个元素为 -1,nums4 的第 1 个元素为 0, - (-1 + 0) = 1,1 在哈希表中,并且 1 的 value 为 1。


所以此时存在四元组(i, j, k, l) = (1, 1, 0, 0),相加为 0,cnt = 1。

image.png

遍历完 nums3 和 nums4 的所有元素,找到 2 个四元组 (1, 1, 0, 0) 和 (0, 0, 0, 1),此时 cnt = 2。

# 统计剩余两个数组的和,在哈希表中找是否存在相加为 0 的情况。
for n3 in nums3:
    for n4 in nums4:
        if -(n3 + n4) in hash:
            cnt += hash[-(n3 + n4)]

本题解法用了两次双重循环,时间复杂度为 O(n²)


同时额外维护了一个哈希表,最坏情况下 nums1[i] + nums[j] 的值全不相同,所以空间复杂度为 O(n²)


代码实现


Python 代码实现

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        # 初始化哈希表
        hash = {}
        cnt = 0
        # 首先存储前两个数组之和
        for n1 in nums1:
            for n2 in nums2:
                # 如果在哈希表中,则对应哈希值 +1
                if n1 + n2 in hash:
                    hash[n1 + n2] += 1
                # 如果不在哈希表中,放入哈希表
                else:
                    hash[n1 + n2] = 1
        # 统计剩余两个数组的和,在哈希表中找是否存在相加为 0 的情况。
        for n3 in nums3:
            for n4 in nums4:
                if -(n3 + n4) in hash:
                    cnt += hash[-(n3 + n4)]
        return cnt

Java 代码实现

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

图解四数相加Ⅱ到这就结束辣,哈希实战系列到这就初步结束啦。

为啥是初步?当然是后面碰到哈希好题会继续加塞。


希望这几道哈希实战题能让你找到点儿感觉,以此为支撑,去搞更复杂更难的题。


大家加油!别忘了我的点赞+在看呀。


我是帅蛋,我们下次见!


相关文章
|
算法 Java Python
ACM 选手图解 LeetCode 二叉搜索树中的搜索
ACM 选手图解 LeetCode 二叉搜索树中的搜索
ACM 选手图解 LeetCode 二叉搜索树中的搜索
|
算法 Java Python
ACM 选手图解 LeetCode 对称二叉树
ACM 选手图解 LeetCode 对称二叉树
ACM 选手图解 LeetCode 对称二叉树
|
Java 数据安全/隐私保护 Python
ACM 选手图解 LeetCode 验证二叉搜索树
ACM 选手图解 LeetCode 验证二叉搜索树
ACM 选手图解 LeetCode 验证二叉搜索树
|
存储 Java Python
ACM 选手图解 LeetCode 二叉树的层平均值
ACM 选手图解 LeetCode 二叉树的层平均值
ACM 选手图解 LeetCode 二叉树的层平均值
|
Java Python
ACM 选手图解 LeetCode 二叉树的右视图
ACM 选手图解 LeetCode 二叉树的右视图
ACM 选手图解 LeetCode 二叉树的右视图
|
Java Python
ACM 选手图解 LeetCode 二叉树的层序遍历Ⅱ
ACM 选手图解 LeetCode 二叉树的层序遍历Ⅱ
ACM 选手图解 LeetCode 二叉树的层序遍历Ⅱ
|
Java Python
ACM 选手图解 LeetCode 二叉树的最近公共祖先
ACM 选手图解 LeetCode 二叉树的最近公共祖先
ACM 选手图解 LeetCode 二叉树的最近公共祖先
|
存储 算法 Java
ACM 选手图解 LeetCode 合并二叉树
ACM 选手图解 LeetCode 合并二叉树
ACM 选手图解 LeetCode 合并二叉树
|
算法 Java Python
ACM 选手图解 LeetCode 最大二叉树
ACM 选手图解 LeetCode 最大二叉树
ACM 选手图解 LeetCode 最大二叉树
|
算法 Java Python
ACM 选手图解 LeetCode 路径总和
ACM 选手图解 LeetCode 路径总和
ACM 选手图解 LeetCode 路径总和