哈希算法题目：四数之和 II

字数 2317 2025-10-27 19:14:05

哈希算法题目：四数之和 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

解题过程

问题分析
最直观的解法是使用四重循环，分别遍历四个数组，检查所有可能的 (i, j, k, l) 组合，看它们的和是否为0。这种方法的时间复杂度是 O(n⁴)，当数组长度 n 较大时（例如 n=200），计算量会达到 1.6亿次，这是不可接受的。我们需要寻找更高效的算法。
核心思路：分组 + 哈希表
我们可以将四个数组分成两组。将问题转化为：寻找 A + B + C + D = 0，等价于寻找 A + B = -(C + D)。
- 步骤一：我们先遍历数组 nums1 和 nums2，计算所有可能的元素对 (i, j) 的和（即 nums1[i] + nums2[j]）。
- 步骤二：使用一个哈希表（在 Python 中是字典）来记录这些和以及每个和出现的次数。例如，如果 1 + 2 = 3 和 0 + 3 = 3，那么和 3 在哈希表中对应的值就是 2。
- 步骤三：然后，我们遍历数组 nums3 和 nums4，计算所有可能的元素对 (k, l) 的和（即 nums3[k] + nums4[l]）。
- 步骤四：对于在 nums3 和 nums4 中计算出的每一个和，我们检查其相反数（即 -(nums3[k] + nums4[l])）是否存在于步骤二建立的哈希表中。如果存在，那么哈希表中这个相反数对应的值（即出现的次数），就是当前 (k, l) 对能够与步骤一中的若干 (i, j) 对组合成满足条件 (A+B) + (C+D) = 0 的有效元组的个数。
详细步骤与示例
假设我们有四个数组：
nums1 = [1, 2]
nums2 = [-2, -1]
nums3 = [-1, 2]
nums4 = [0, 2]
- 第一步：处理前两个数组 (nums1 和 nums2)
  我们计算所有可能的和，并构建哈希表 sum_count。
  - nums1[0] + nums2[0] = 1 + (-2) = -1
  - nums1[0] + nums2[1] = 1 + (-1) = 0
  - nums1[1] + nums2[0] = 2 + (-2) = 0
  - nums1[1] + nums2[1] = 2 + (-1) = 1
  此时，我们的哈希表 sum_count 内容如下：
  Key (和的值): -1, 0, 0, 1
  我们记录每个和出现的次数：
  sum_count = {-1: 1, 0: 2, 1: 1}
- 第二步：处理后两个数组 (nums3 和 nums4)
  我们计算所有可能的和，并检查其相反数是否在哈希表中。
  - nums3[0] + nums4[0] = (-1) + 0 = -1。我们需要找的相反数是 -(-1) = 1。检查哈希表，1 出现了 1 次。所以，当前组合贡献了 1 个有效元组。
  - nums3[0] + nums4[1] = (-1) + 2 = 1。相反数是 -1。-1 在哈希表中出现了 1 次。贡献 1 个元组。
  - nums3[1] + nums4[0] = 2 + 0 = 2。相反数是 -2。-2 不在哈希表中，贡献 0 个元组。
  - nums3[1] + nums4[1] = 2 + 2 = 4。相反数是 -4。-4 不在哈希表中，贡献 0 个元组。
- 第三步：统计结果
  将所有贡献相加：1 + 1 + 0 + 0 = 2。
  因此，满足条件的元组一共有 2 个。
  
  我们可以验证一下这两个元组：
  1. (i=0, j=1, k=0, l=1): nums1[0] + nums2[1] + nums3[0] + nums4[1] = 1 + (-1) + (-1) + 2 = 1
    （这里计算有误，让我们重新验证）
    重新计算示例：
    有效元组1: (i=0, j=0, k=1, l=0): 1 + (-2) + 2 + 0 = 1? (不等于0，无效)
    有效元组应来自我们的算法逻辑：
    算法找到的第一个：当 (k,l) 是 (0,0) 即 (-1,0) 和为 -1，需要 A+B=1。哈希表中 A+B=1 的情况是 (i=1, j=1) 即 (2, -1)。所以元组是 (1,1,0,0): 2 + (-1) + (-1) + 0 = 0。正确。
    算法找到的第二个：当 (k,l) 是 (0,1) 即 (-1,2) 和为 1，需要 A+B=-1。哈希表中 A+B=-1 的情况是 (i=0, j=0) 即 (1, -2)。所以元组是 (0,0,0,1): 1 + (-2) + (-1) + 2 = 0。正确。
    所以结果是 2 个元组: (1,1,0,0) 和 (0,0,0,1)。
算法总结
- 时间复杂度：O(n²)。我们有两个独立的双重循环，每个循环的时间复杂度都是 O(n²)。
- 空间复杂度：O(n²)。在最坏情况下，前两个数组产生的所有和可能都不同，哈希表需要存储 O(n²) 个键值对。
这种方法通过巧妙地运用哈希表，将原本 O(n⁴) 的问题优化到了 O(n²)，是典型的以空间换时间的策略。

哈希算法题目：四数之和 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 解题过程问题分析最直观的解法是使用四重循环，分别遍历四个数组，检查所有可能的 (i, j, k, l) 组合，看它们的和是否为0。这种方法的时间复杂度是 O(n⁴)，当数组长度 n 较大时（例如 n=200），计算量会达到 1.6亿次，这是不可接受的。我们需要寻找更高效的算法。核心思路：分组 + 哈希表我们可以将四个数组分成两组。将问题转化为：寻找 A + B + C + D = 0，等价于寻找 A + B = -(C + D)。步骤一：我们先遍历数组 nums1 和 nums2，计算所有可能的元素对 (i, j) 的和（即 nums1[i] + nums2[j] ）。步骤二：使用一个哈希表（在 Python 中是字典）来记录这些和以及每个和出现的次数。例如，如果 1 + 2 = 3 和 0 + 3 = 3 ，那么和 3 在哈希表中对应的值就是 2。步骤三：然后，我们遍历数组 nums3 和 nums4，计算所有可能的元素对 (k, l) 的和（即 nums3[k] + nums4[l] ）。步骤四：对于在 nums3 和 nums4 中计算出的每一个和，我们检查其相反数（即 -(nums3[k] + nums4[l]) ）是否存在于步骤二建立的哈希表中。如果存在，那么哈希表中这个相反数对应的值（即出现的次数），就是当前 (k, l) 对能够与步骤一中的若干 (i, j) 对组合成满足条件 (A+B) + (C+D) = 0 的有效元组的个数。详细步骤与示例假设我们有四个数组： nums1 = [ 1, 2 ] nums2 = [ -2, -1 ] nums3 = [ -1, 2 ] nums4 = [ 0, 2 ] 第一步：处理前两个数组 (nums1 和 nums2) 我们计算所有可能的和，并构建哈希表 sum_count 。 nums1[ 0] + nums2[ 0 ] = 1 + (-2) = -1 nums1[ 0] + nums2[ 1 ] = 1 + (-1) = 0 nums1[ 1] + nums2[ 0 ] = 2 + (-2) = 0 nums1[ 1] + nums2[ 1 ] = 2 + (-1) = 1 此时，我们的哈希表 sum_count 内容如下： Key (和的值): -1, 0, 0, 1 我们记录每个和出现的次数： sum_count = {-1: 1, 0: 2, 1: 1} 第二步：处理后两个数组 (nums3 和 nums4) 我们计算所有可能的和，并检查其相反数是否在哈希表中。 nums3[ 0] + nums4[ 0] = (-1) + 0 = -1。我们需要找的相反数是 -(-1) = 1 。检查哈希表， 1 出现了 1 次。所以，当前组合贡献了 1 个有效元组。 nums3[ 0] + nums4[ 1] = (-1) + 2 = 1。相反数是 -1 。 -1 在哈希表中出现了 1 次。贡献 1 个元组。 nums3[ 1] + nums4[ 0] = 2 + 0 = 2。相反数是 -2 。 -2 不在哈希表中，贡献 0 个元组。 nums3[ 1] + nums4[ 1] = 2 + 2 = 4。相反数是 -4 。 -4 不在哈希表中，贡献 0 个元组。第三步：统计结果将所有贡献相加：1 + 1 + 0 + 0 = 2。因此，满足条件的元组一共有 2 个。我们可以验证一下这两个元组： (i=0, j=1, k=0, l=1): nums1[ 0] + nums2[ 1] + nums3[ 0] + nums4[ 1 ] = 1 + (-1) + (-1) + 2 = 1 （这里计算有误，让我们重新验证）重新计算示例：有效元组1: (i=0, j=0, k=1, l=0): 1 + (-2) + 2 + 0 = 1? (不等于0，无效) 有效元组应来自我们的算法逻辑：算法找到的第一个：当 (k,l) 是 (0,0) 即 (-1,0) 和为 -1，需要 A+B=1。哈希表中 A+B=1 的情况是 (i=1, j=1) 即 (2, -1)。所以元组是 (1,1,0,0): 2 + (-1) + (-1) + 0 = 0。正确。算法找到的第二个：当 (k,l) 是 (0,1) 即 (-1,2) 和为 1，需要 A+B=-1。哈希表中 A+B=-1 的情况是 (i=0, j=0) 即 (1, -2)。所以元组是 (0,0,0,1): 1 + (-2) + (-1) + 2 = 0。正确。所以结果是 2 个元组: (1,1,0,0) 和 (0,0,0,1)。算法总结时间复杂度：O(n²)。我们有两个独立的双重循环，每个循环的时间复杂度都是 O(n²)。空间复杂度：O(n²)。在最坏情况下，前两个数组产生的所有和可能都不同，哈希表需要存储 O(n²) 个键值对。这种方法通过巧妙地运用哈希表，将原本 O(n⁴) 的问题优化到了 O(n²)，是典型的以空间换时间的策略。