题目

标题和出处

标题：四数之和 II

出处：454. 四数之和 II

难度

6 级

题目描述

要求

给你四个整数数组 $\text{nums1}$、$\text{nums2}$、$\text{nums3}$ 和 $\text{nums4}$，数组长度都是 $\text{n}$，请你计算有多少个元组 $\text{(i, j, k, l)}$ 能满足：

• $\text{0}\le \text{i, j, k, l}<\text{n}$
• $\text{nums1[i] + nums2[j] + nums3[k] + nums4[l]}=\text{0}$

示例

示例 1：

输入：$\text{nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]}$
输出：$\text{2}$
解释：
两个元组如下：

1. $\text{(0, 0, 0, 1)}\to \text{nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0}$
2. $\text{(1, 1, 0, 0)}\to \text{nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0}$

示例 2：

输入：$\text{nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]}$
输出：$\text{1}$

数据范围

• $\text{n}=\text{nums1.length}$
• $\text{n}=\text{nums2.length}$
• $\text{n}=\text{nums3.length}$
• $\text{n}=\text{nums4.length}$
• $\text{1}\le \text{n}\le \text{200}$
• -2 28 ≤ nums1[i], nums2[i], nums3[i], nums4[i] ≤ 2 28 \\texttt{-2}^\\texttt{28} \\le \\texttt{nums1[i], nums2[i], nums3[i], nums4[i]} \\le \\texttt{2}^\\texttt{28} -228≤nums1[i], nums2[i], nums3[i], nums4[i]≤228

解法

思路和算法

这道题要求计算使得四个数组中的元素和为 $0$ 的下标四元组的数量。最直观的做法是使用四重循环遍历四个数组，对于四个长度为 $n$ 的数组，该做法的时间复杂度是 O ( n 4 ) O(n^4) O(n4)，该时间复杂度过高，需要优化。

可以将四个数组分成两组， nums 1 \\textit{nums}_1 nums1​ 和 nums 2 \\textit{nums}_2 nums2​ 为第一组， nums 3 \\textit{nums}_3 nums3​ 和 nums 4 \\textit{nums}_4 nums4​ 为第二组。对于第一组，使用二重循环遍历所有的下标对 $(i,j)$，计算 nums 1 [ i ] + nums 2 [ j ] \\textit{nums}_1[i] + \\textit{nums}_2[j] nums1​[i]+nums2​[j] 的值，并使用哈希表记录每对元素和以及出现次数，时间复杂度是 O ( n 2 ) O(n^2) O(n2)。

得到第一组的每对元素和以及出现次数之后，对于第二组，同样使用二重循环遍历所有的下标对 $(k,l)$，计算 nums 3 [ k ] + nums 4 [ l ] \\textit{nums}_3[k] + \\textit{nums}_4[l] nums3​[k]+nums4​[l] 的值，并计算符合要求的四元素的数量，时间复杂度是 O ( n 2 ) O(n^2) O(n2)。具体做法如下：令 sum = nums 3 [ k ] + nums 4 [ l ] \\textit{sum} = \\textit{nums}_3[k] + \\textit{nums}_4[l] sum=nums3​[k]+nums4​[l]，从哈希表中得到元素和 $-\text{sum}$ 的出现次数 $\text{count}$（如果哈希表中不存在元素和 $-\text{sum}$ 则 $\text{count}=0$），由于每对元素和 $-\text{sum}$ 都可以和当前的 $\text{sum}$ 组成一个符合要求的四元组，因此将 $\text{count}$ 加到符合要求的四元组的数量中。

实现方面，由于只需要知道符合要求的四元组的数量，不需要知道每个四元组的具体值，因此可以直接遍历每个数组中的元素，不需要记录下标。

代码

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int tuplesCount = 0;Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int num1 : nums1) {for (int num2 : nums2) {int sum = num1 + num2;map.put(sum, map.getOrDefault(sum, 0) + 1);}}for (int num3 : nums3) {for (int num4 : nums4) {int sum = num3 + num4;int count = map.getOrDefault(-sum, 0);tuplesCount += count;}}return tuplesCount;}
}

复杂度分析

• 时间复杂度： O ( n 2 ) O(n^2) O(n2)，其中 $n$ 是每个数组的长度。对数组 nums 1 \\textit{nums}_1 nums1​ 和 nums 2 \\textit{nums}_2 nums2​ 以及对数组 nums 3 \\textit{nums}_3 nums3​ 和 nums 4 \\textit{nums}_4 nums4​ 各需要执行一次两重循环，每次两重循环的时间复杂度是 O ( n 2 ) O(n^2) O(n2)，由于哈希表操作的时间都是 $O(1)$，因此总时间复杂度是 O ( n 2 ) O(n^2) O(n2)。

• 空间复杂度： O ( n 2 ) O(n^2) O(n2)，其中 $n$ 是每个数组的长度。需要使用哈希表存储数组 nums 1 \\textit{nums}_1 nums1​ 和 nums 2 \\textit{nums}_2 nums2​ 中的每对元素和以及出现次数，哈希表中的元素个数不会超过 n 2 n^2 n2。