一、问题描述

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

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 $0 \leq N \leq 500$。所有整数的范围在 $-2^{28}$ 到 $2^{28} - 1$ 之间，最终结果不会超过 $2^{31} - 1$。

示例：

输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解释:
两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

二、方案一：暴力法

1、思路

暴力法是最直观的方法。通过四层循环遍历所有可能的元组组合，然后计算它们的和，检查是否等于 0。

2、代码实现

func fourSumCount(A []int, B []int, C []int, D []int) int {
    count := 0
    for i := 0; i < len(A); i++ {
        for j := 0; j < len(B); j++ {
            for k := 0; k < len(C); k++ {
                for l := 0; l < len(D); l++ {
                    if A[i]+B[j]+C[k]+D[l] == 0 {
                        count++
                    }
                }
            }
        }
    }
    return count
}

3、复杂度分析

• 时间复杂度：O(n^4)，其中 n 是数组 A, B, C, D 的长度。
• 空间复杂度：O(1)，因为只使用了常数级别的额外空间。

三、方案二：哈希表法

1、思路

使用哈希表来优化查找过程。首先计算 A 和 B 的所有可能组合的和，并将它们存储在哈希表中，键为和，值为出现的次数。然后，对于 C 和 D 的每个组合，查找 0 - (C[k] + D[l]) 在哈希表中的出现次数，累加所有的次数得到最终答案。

2、代码实现

func fourSumCount(A []int, B []int, C []int, D []int) int {
    sumMap := make(map[int]int)
    for _, a := range A {
        for _, b := range B {
            sumMap[a+b]++
        }
    }
    count := 0
    for _, c := range C {
        for _, d := range D {
            count += sumMap[0-c-d]
        }
    }
    return count
}

3、复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组 A, B, C, D 的长度。我们需要计算 A 和 B 的所有组合的和，以及遍历 C 和 D。
• 空间复杂度：O(n^2)，因为我们需要存储 A 和 B 的所有组合的和及其出现的次数。

四、总结

方案	时间复杂度	空间复杂度	优点	缺点
暴力法	O(n^4)	O(1)	实现简单	效率极低
哈希表法	O(n^2)	O(n^2)	效率高	需要额外空间

推荐使用哈希表法，因为它在效率上远优于暴力法，虽然需要额外的空间。