454. 四数相加 II

454. 四数相加 II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

方法一：分组 + 哈希表

思路与算法
我们可以将四个数组分成两部分，AA 和 BB 为一组，CC 和 DD 为另外一组。
对于 AA 和 BB，我们使用二重循环对它们进行遍历，得到所有 A[i]+B[j]A[i]+B[j] 的值并存入哈希映射中。对于哈希映射中的每个键值对，每个键表示一种 A[i]+B[j]A[i]+B[j]，对应的值为 A[i]+B[j]A[i]+B[j] 出现的次数。
对于 CC 和 DD，我们同样使用二重循环对它们进行遍历。当遍历到 C[k]+D[l]C[k]+D[l] 时，如果 -(C[k]+D[l])−(C[k]+D[l]) 出现在哈希映射中，那么将 -(C[k]+D[l])−(C[k]+D[l]) 对应的值累加进答案中。
最终即可得到满足 A[i]+B[j]+C[k]+D[l]=0A[i]+B[j]+C[k]+D[l]=0 的四元组数目。

复杂度分析

• 时间复杂度：O(n^2)。我们使用了两次二重循环，时间复杂度均为 O(n^2)。在循环中对哈希映射进行的修改以及查询操作的期望时间复杂度均为 O(1)，因此总时间复杂度为 O(n^2)。
  

• 空间复杂度：O(n^2)，即为哈希映射需要使用的空间。在最坏的情况下，A[i]+B[j]A[i]+B[j] 的值均不相同，因此值的个数为 n^2，也就需要 O(n^2)的空间。
  

  func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    var res int
    countAB := map[int]int{}
    for _, v1 := range nums1 {
        for _, v2 := range nums2 {
            countAB[v1 + v2]++
        }
    }
    for _, v3 := range nums3 {
        for _, v4 := range nums4 {
            if countAB, ok := countAB[-v3-v4]; ok {
                res = res + countAB
            }
        }
    }
    return res
  }