📃 题目描述

题目链接：454. 四数相加 II - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定四个包含整数的数组列表 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 。所有整数的范围在 到 之间，最终结果不会超过 。

例如:

输入:

A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

输出:

2

解释:

两个元组如下:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

🔔 解题思路

注意返回值是满足条件的元组的个数。

本题涉及四个数组，暴力解法就是四层循环，显然不可取，我们考虑两两处理的方式，具体步骤如下：

首先定义变量 count，用来统计符合条件的元组的个数，即（a+b）+（c+d）= 0 出现的次数，然后：

1）先处理 A 数组和 B 数组：

• 定义一个 Map，key 存放 a 和 b 两数之和，value 存放 a 和 b 两数之和出现的次数
• 遍历 A 和 B 数组，统计两个数组元素之和以及出现的次数，放到 map 中

2）再处理 C 数组和 D 数组

• 遍历 C 和 D 数组，如果 0-(c+d) 这个 key 在 map 中出现过的话，即表示这 a b c d 是一个符合条件的元组，count 加上 map 中 key 是 0-(c+d) 对应的 value 即可

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int count = 0;  

        // key 存放 a 和 b 两数之和，value 存放 a 和 b 两数之和出现的次数
        Map<Integer, Integer> map = new HashMap<>();

        // 处理 A 数组和 B 数组
        for (int a : nums1) {
            for (int b : nums2) {
                int temp = a + b;
                map.put(temp, map.getOrDefault(temp, 0) + 1);
            }
        }

        // 再处理 C 数组和 D 数组
        for (int c : nums3) {
            for (int d : nums4) {
                int temp = c + d;
                // 如果 0-(c+d) 这个 key 在 map 中出现过的话, 即表示这 a b c d 是一个符合条件的元组
                if (map.containsKey(0 - temp)) {
                    count += map.get(0 - temp);
                }
            }
        }

        return count;
    
    }
}

💥 复杂度分析

• 空间复杂度：HasMap 中处理了两个数组的所有组合，所以空间复杂度为 O(N^2)
• 时间复杂度：一共两个两层循环，O(N^2) + O(N^2) = O(N^2)