四数相加 II

标签: 数组 哈希表

难度: Medium

给你四个整数数组 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

Submission

运行时间: 189 ms

内存: 16.2 MB

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        from collections import Counter
        nums1 = Counter(nums1)
        nums2 = Counter(nums2)
        nums3 = Counter(nums3)
        nums4 = Counter(nums4)
        ans = 0
        sum12 = defaultdict(int)
        for i, j in nums1.items() :
            for k, l in nums2.items() :
                sum12[i + k] += j * l

        for i, j in nums3.items() :
            for k, l in nums4.items() :
                target = -(i + k)
                ans += sum12[target] * j * l
        return ans

Explain

这个题解采用了哈希表的思路。首先，对四个数组分别进行计数，然后遍历nums1和nums2的计数结果，记录它们元素和的频次。接着遍历nums3和nums4的计数结果，查找哈希表中是否存在与当前两数之和相反数的键，如果存在，则将对应的值（即出现频次）累加到答案中。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        from collections import Counter
        nums1 = Counter(nums1)  # 对nums1进行计数
        nums2 = Counter(nums2)  # 对nums2进行计数
        nums3 = Counter(nums3)  # 对nums3进行计数
        nums4 = Counter(nums4)  # 对nums4进行计数
        ans = 0
        sum12 = defaultdict(int)  # 存储nums1和nums2元素和的频次
        for i, j in nums1.items() :
            for k, l in nums2.items() :
                sum12[i + k] += j * l  # 计算nums1和nums2元素和的频次

        for i, j in nums3.items() :
            for k, l in nums4.items() :
                target = -(i + k)  # 计算目标值
                ans += sum12[target] * j * l  # 累加满足条件的频次
        return ans

Explore

选择遍历nums1和nums2来记录元素和的频次而不是nums3和nums4主要是基于算法的对称性和实现的方便性。在四数相加的问题中，无论是先计算nums1和nums2的元素和还是nums3和nums4的元素和，本质上没有区别，因为都是为了生成一个中间结果的哈希表，用以匹配另外两个数组元素和的相反数。性能影响主要取决于哪两个数组组合生成的和的唯一值最少，这样可以减少哈希表的大小，从而优化空间复杂度和可能的查找时间。如果nums1和nums2的组合比nums3和nums4生成更少的唯一和，那么首先处理nums1和nums2是更优的选择。

如果输入数组包含大量重复元素，这将对算法的性能产生正面影响。因为重复元素减少了数组元素和的多样性，从而减少了哈希表中需要存储的键的数量。这意味着空间复杂度会降低，并且查找匹配和的操作也将更快，因为哈希表的大小减小了。此外，计算元素和的过程中，重复元素可以通过Counter直接得到其频次，减少了计算时间。

如果nums1和nums2的长度远大于nums3和nums4，可以考虑首先处理长度较小的数组组合（nums3和nums4），并计算它们元素和的频次，这是因为小数组组合的元素和的唯一值可能更少，从而生成的哈希表更小。这样，当我们在处理较大数组组合（nums1和nums2）时，查找和匹配的操作将在一个较小的哈希表上进行，这可以减少查找的时间复杂度，并且使用较少的空间。此外，这也减少了需要计算的总和的数量，可能进一步优化算法的效率。