四数相加 II
难度:
标签:
题目描述
给你四个整数数组 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
-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
代码结果
运行时间: 189 ms, 内存: 16.2 MB
/*
* 思路:
* 1. 使用 Java Stream API 计算 nums1 和 nums2 的两两和,并存入 Map 中。
* 2. 使用 Java Stream API 遍历 nums3 和 nums4,并计算其两两和的相反数在 Map 中的出现次数。
* 3. 最后返回结果。
*/
import java.util.HashMap;
import java.util.Map;
import java.util.Arrays;
public class FourSumCountStream {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<>();
Arrays.stream(nums1).forEach(i ->
Arrays.stream(nums2).forEach(j ->
map.put(i + j, map.getOrDefault(i + j, 0) + 1)
)
);
return Arrays.stream(nums3).flatMap(k ->
Arrays.stream(nums4).mapToObj(l -> -(k + l))
).mapToInt(sum -> map.getOrDefault(sum, 0)).sum();
}
}
解释
方法:
这个题解采用了哈希表的思路。首先,对四个数组分别进行计数,然后遍历nums1和nums2的计数结果,记录它们元素和的频次。接着遍历nums3和nums4的计数结果,查找哈希表中是否存在与当前两数之和相反数的键,如果存在,则将对应的值(即出现频次)累加到答案中。
时间复杂度:
O(n^2)
空间复杂度:
O(n^2)
代码细节讲解
🦆
在题解的算法中,为什么选择首先遍历nums1和nums2来记录元素和的频次,而不是nums3和nums4,这种选择对性能有何影响?
▷🦆
在实际应用中,如果输入数组包含大量重复元素,这种情况会对算法的性能产生怎样的影响?
▷🦆
如果数组的长度非常不均匀,比如nums1和nums2远大于nums3和nums4,这种情况下如何优化算法以提高效率?
▷相关问题
四数之和
给你一个由 n
个整数组成的数组 nums
,和一个目标值 target
。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a
、b
、c
和d
互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0 输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2:
输入:nums = [2,2,2,2,2], target = 8 输出:[[2,2,2,2]]
提示:
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109