题目
标题和出处
标题：四数之和 II
出处：454. 四数之和 II
难度
6 级
题目描述
要求
给你四个整数数组 nums1 \texttt{nums1} nums1、 nums2 \texttt{nums2} nums2、 nums3 \texttt{nums3} nums3 和 nums4 \texttt{nums4} nums4，数组长度都是 n \texttt{n} n，请你计算有多少个元组 (i, j, k, l) \texttt{(i, j, k, l)} (i, j, k, l) 能满足：
- 0 ≤ i, j, k, l < n \texttt{0} \le \texttt{i, j, k, l} < \texttt{n} 0≤i, j, k, l<n
- nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0 \texttt{nums1[i] + nums2[j] + nums3[k] + nums4[l]} = \texttt{0} nums1[i] + nums2[j] + nums3[k] + nums4[l]=0
示例
示例 1：
输入： nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2] \texttt{nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]} nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出： 2 \texttt{2} 2
解释：
两个元组如下：
- (0, 0, 0, 1) → nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0 \texttt{(0, 0, 0, 1)} \rightarrow \texttt{nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0} (0, 0, 0, 1)→nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) → nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0 \texttt{(1, 1, 0, 0)} \rightarrow \texttt{nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0} (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] \texttt{nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]} nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出： 1 \texttt{1} 1
数据范围
- n = nums1.length \texttt{n} = \texttt{nums1.length} n=nums1.length
- n = nums2.length \texttt{n} = \texttt{nums2.length} n=nums2.length
- n = nums3.length \texttt{n} = \texttt{nums3.length} n=nums3.length
- n = nums4.length \texttt{n} = \texttt{nums4.length} n=nums4.length
- 1 ≤ n ≤ 200 \texttt{1} \le \texttt{n} \le \texttt{200} 1≤n≤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 0 0 的下标四元组的数量。最直观的做法是使用四重循环遍历四个数组，对于四个长度为 n n 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 ) (i, j) (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 ) (k, l) (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]，从哈希表中得到元素和 − sum -\textit{sum} −sum 的出现次数 count \textit{count} count（如果哈希表中不存在元素和 − sum -\textit{sum} −sum 则 count = 0 \textit{count} = 0 count=0），由于每对元素和 − sum -\textit{sum} −sum 都可以和当前的 sum \textit{sum} sum 组成一个符合要求的四元组，因此将 count \textit{count} 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 n 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(1) O(1)，因此总时间复杂度是 O ( n 2 ) O(n^2) O(n2)。
-
空间复杂度： O ( n 2 ) O(n^2) O(n2)，其中 n n n 是每个数组的长度。需要使用哈希表存储数组 nums 1 \textit{nums}_1 nums1 和 nums 2 \textit{nums}_2 nums2 中的每对元素和以及出现次数，哈希表中的元素个数不会超过 n 2 n^2 n2。