454-四数相加 ii

题目地址(454. 四数相加 II - 力扣（LeetCode）)

https://leetcode.cn/problems/4sum-ii/description/

题目描述

给你四个整数数组 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：

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

示例 2：

  输入： nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
 输出： 1

 

  提示：

• 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

前置知识

• 两数之和思路

思路

使用一个哈希表map存储 A 和 B 所有和sumAB的情况，其中 key 是和，value是和出现的次数

使用同样的遍历方式，遍历 C + D，找到map是否存在 −(sumCD)。

将 −(sumCD) 对应的值累加起来，就是答案。

代码

• 语言支持：Java

Java Code:

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> countAB = new HashMap<Integer, Integer>();
        for (int u : A) {
            for (int v : B) {
                countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);
            }
        }
        int ans = 0;
        for (int u : C) {
            for (int v : D) {
                if (countAB.containsKey(-u - v)) {
                    ans += countAB.get(-u - v);
                }
            }
        }
        return ans;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n^2)$：使用双重循环进行遍历求和，其中哈希表操作都是 $O(1)$
• 空间复杂度：$O(n^2)$：哈希表所用的空间，最坏情况下，A 和 B 数组中每个元素之和都不相同。