leetcode
leetcode 401 ~ 450
四数相加 II

四数相加 II

难度:

标签:

题目描述

给你四个整数数组 nums1nums2nums3nums4 ,数组长度都是 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主要是基于算法的对称性和实现的方便性。在四数相加的问题中,无论是先计算nums1和nums2的元素和还是nums3和nums4的元素和,本质上没有区别,因为都是为了生成一个中间结果的哈希表,用以匹配另外两个数组元素和的相反数。性能影响主要取决于哪两个数组组合生成的和的唯一值最少,这样可以减少哈希表的大小,从而优化空间复杂度和可能的查找时间。如果nums1和nums2的组合比nums3和nums4生成更少的唯一和,那么首先处理nums1和nums2是更优的选择。
🦆
在实际应用中,如果输入数组包含大量重复元素,这种情况会对算法的性能产生怎样的影响?
如果输入数组包含大量重复元素,这将对算法的性能产生正面影响。因为重复元素减少了数组元素和的多样性,从而减少了哈希表中需要存储的键的数量。这意味着空间复杂度会降低,并且查找匹配和的操作也将更快,因为哈希表的大小减小了。此外,计算元素和的过程中,重复元素可以通过Counter直接得到其频次,减少了计算时间。
🦆
如果数组的长度非常不均匀,比如nums1和nums2远大于nums3和nums4,这种情况下如何优化算法以提高效率?
如果nums1和nums2的长度远大于nums3和nums4,可以考虑首先处理长度较小的数组组合(nums3和nums4),并计算它们元素和的频次,这是因为小数组组合的元素和的唯一值可能更少,从而生成的哈希表更小。这样,当我们在处理较大数组组合(nums1和nums2)时,查找和匹配的操作将在一个较小的哈希表上进行,这可以减少查找的时间复杂度,并且使用较少的空间。此外,这也减少了需要计算的总和的数量,可能进一步优化算法的效率。

相关问题

四数之和

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

  • 0 <= a, b, c, d < n
  • abcd 互不相同
  • 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