哈希算法题目：四数相加 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 == nums2.length == nums3.length == nums4.length
• 1 <= n <= 200
• -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

解题过程

这个问题如果使用暴力解法，需要四重循环枚举所有 (i, j, k, l) 的组合，时间复杂度为 O(n^4)，在 n 最大为 200 时计算量太大（200^4 = 1.6×10^9），显然不可行。

第一步：核心思路——化四为二

哈希表的核心作用是以空间换时间，通过存储中间结果来避免重复计算。

观察题目，四个数组的地位是对称的。我们可以将问题拆分为两组：

1. 先计算 nums1 和 nums2 中所有可能的元素和，并将这些和及其出现次数存储在一个哈希表中。
2. 再遍历 nums3 和 nums4 中所有可能的元素和，检查哈希表中是否存在其相反数。

为什么这样做？
因为如果 nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0，那么：
nums1[i] + nums2[j] = - (nums3[k] + nums4[l])

所以，我们只需要：

• 统计所有 a + b（其中 a 来自 nums1，b 来自 nums2）的和以及每个和出现的次数。
• 对于所有 c + d（其中 c 来自 nums3，d 来自 nums4），在哈希表中查找 -(c + d) 出现的次数，并累加。

这样，我们就将时间复杂度从 O(n^4) 降低到了 O(n^2)。

第二步：详细步骤拆解

步骤1：创建并填充第一个哈希表

• 初始化一个空的哈希表（例如 Python 的 defaultdict(int) 或 C++ 的 unordered_map），键是两数之和，值是该和出现的次数。
• 使用双重循环遍历 nums1 和 nums2 的所有元素：
  • 计算和 sum_ab = a + b。
  • 在哈希表中，将键 sum_ab 对应的值加 1（即出现次数增加）。

步骤2：遍历后两个数组并计数

• 初始化结果计数器 count = 0。
• 使用双重循环遍历 nums3 和 nums4 的所有元素：
  • 计算和 sum_cd = c + d。
  • 计算目标值 target = -sum_cd。
  • 在哈希表中查找 target：
    • 如果 target 存在于哈希表中，则将 target 对应的值（即前面计算出的出现次数）累加到 count 中。
    • 如果不存在，则跳过。

步骤3：返回结果

• 循环结束后，count 就是满足条件的元组总数，返回 count。

第三步：举例说明

以示例1为例：

• nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]

步骤1：构建哈希表（统计 nums1 和 nums2 的和）

• 可能的和：
  • 1 + (-2) = -1
  • 1 + (-1) = 0
  • 2 + (-2) = 0
  • 2 + (-1) = 1
• 哈希表内容：{-1: 1, 0: 2, 1: 1}

步骤2：遍历 nums3 和 nums4，查找相反数

1. c = -1, d = 0: sum_cd = -1, target = 1。哈希表中 1 出现 1 次 → count = 1
2. c = -1, d = 2: sum_cd = 1, target = -1。哈希表中 -1 出现 1 次 → count = 2
3. c = 2, d = 0: sum_cd = 2, target = -2。哈希表中无 -2 → 跳过
4. c = 2, d = 2: sum_cd = 4, target = -4。哈希表中无 -4 → 跳过

结果：count = 2，与示例输出一致。

第四步：复杂度分析

• 时间复杂度：O(n^2)。我们有两个嵌套循环遍历前两个数组（O(n^2)），以及两个嵌套循环遍历后两个数组（O(n^2)），总时间复杂度为 O(n^2) + O(n^2) = O(n^2)。
• 空间复杂度：O(n^2)。在最坏情况下，nums1 和 nums2 中所有可能的和都不同，哈希表最多存储 n^2 个键值对。

第五步：关键点与扩展思考

1. 为什么用哈希表？
   因为我们需要快速查找“某个和是否出现过，以及出现过几次”。哈希表的平均查找时间是 O(1)，非常适合这种需求。

2. 哈希冲突如何处理？
   现代编程语言的标准哈希表实现（如 unordered_map）会自动处理冲突，我们不需要手动实现。

3. 可以扩展到更多数组吗？
   可以。例如，对于“六数之和为零”的问题，可以将六个数组分成两组（每组三个），时间复杂度为 O(n^3)。核心思想总是“分组+哈希”。

4. 注意整数范围：
   题目中数字的范围是 -2^28 到 2^28，它们的和可能在 -2^29 到 2^29 之间，在常见编程语言的整数范围内（如 32 位有符号整数可表示到 ±2^31），因此可以直接使用整数作为哈希表的键。

这个题目是哈希表用于“分组+降低复杂度”的经典应用，通过将四数之和问题转化为两个两数之和问题，大幅提升了效率。