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

字数 2524 2025-10-25 22:15:07

哈希算法题目：四数之和 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亿次，效率极低，不可接受。因此，我们需要寻找更优的解法。
核心思路：空间换时间
我们可以将问题拆解。观察等式：nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0。
可以将其转化为：nums1[i] + nums2[j] = - (nums3[k] + nums4[l])。
这个转化是解题的关键。它意味着，前两个数组的元素和，与后两个数组的元素和，互为相反数。
引入哈希表
基于上述思路，我们可以分两步走：
- 第一步：遍历数组 nums1 和 nums2，计算所有可能的和 a + b，并使用一个哈希表（在 Python 中通常用字典 dict）来记录每个和出现的次数。
- 第二步：遍历数组 nums3 和 nums4，计算所有可能的和 c + d，然后查看哈希表中是否存在键 -(c + d)。如果存在，那么就意味着我们找到了 (a+b) + (c+d) = 0 的组合。此时，将哈希表中 -(c + d) 对应的值（即该和出现的次数）累加到结果中。
为什么是累加次数？因为对于某个特定的 -(c + d)，它在哈希表中出现的次数，就等于在 nums1 和 nums2 中有多少种不同的 (i, j) 组合能组成这个和。
详细步骤
让我们通过一个微型例子来一步步验证。设：
nums1 = [1, 2], nums2 = [-1, -2], nums3 = [-1, 2], nums4 = [0, 2]，n=2。

步骤一：构建哈希表（处理前两个数组）
- 初始化一个空字典 hash_map = {}，用于存储和及其出现次数。
- 遍历 nums1 和 nums2：
  - i=0, j=0: 和 = 1 + (-1) = 0。hash_map[0] 目前不存在，我们将其设为 1。hash_map = {0: 1}
  - i=0, j=1: 和 = 1 + (-2) = -1。hash_map[-1] 不存在，设为 1。hash_map = {0: 1, -1: 1}
  - i=1, j=0: 和 = 2 + (-1) = 1。hash_map[1] 不存在，设为 1。hash_map = {0: 1, -1: 1, 1: 1}
  - i=1, j=1: 和 = 2 + (-2) = 0。hash_map[0] 已存在，将其值加 1，变为 2。hash_map = {0: 2, -1: 1, 1: 1}
步骤二：统计结果（处理后两个数组）
- 初始化结果计数器 count = 0。
- 遍历 nums3 和 nums4：
  - k=0, l=0: 和 = (-1) + 0 = -1。我们需要找的键是 -(-1) = 1。检查 hash_map，1 存在，其值为 1。所以 count += 1，现在 count = 1。
  - k=0, l=1: 和 = (-1) + 2 = 1。我们需要找的键是 -(1) = -1。检查 hash_map，-1 存在，其值为 1。所以 count += 1，现在 count = 2。
  - k=1, l=0: 和 = 2 + 0 = 2。我们需要找的键是 -(2) = -2。检查 hash_map，-2 不存在，跳过。
  - k=1, l=1: 和 = 2 + 2 = 4。我们需要找的键是 -(4) = -4。检查 hash_map，-4 不存在，跳过。
- 最终结果 count = 2。
  我们可以验证一下这两个元组：
  - (i=0, j=0, k=0, l=1): 1 + (-1) + (-1) + 2 = (0) + (1) = 1? 不对。让我们仔细核对。
    实际上，根据我们的逻辑：
    - 第一个情况：hash_map[1]=1 对应 (i=1,j=0)，和 c+d=-1 对应 (k=0,l=0)。元组是 (1, 0, 0, 0)：nums1[1]=2, nums2[0]=-1, nums3[0]=-1, nums4[0]=0。和为 2 + (-1) + (-1) + 0 = 0。正确。
    - 第二个情况：hash_map[-1]=1 对应 (i=0,j=1)，和 c+d=1 对应 (k=0,l=1)。元组是 (0, 1, 0, 1)：nums1[0]=1, nums2[1]=-2, nums3[0]=-1, nums4[1]=2。和为 1 + (-2) + (-1) + 2 = 0。正确。
复杂度分析
- 时间复杂度：O(n²)。我们使用了两个独立的双重循环。第一个循环遍历 nums1 和 nums2，计算量为 n * n = n²。第二个循环遍历 nums3 和 nums4，计算量同样为 n²。总时间复杂度为 O(n²) + O(n²) = O(n²)，远优于最初的 O(n⁴)。
- 空间复杂度：O(n²)。在最坏情况下，nums1 和 nums2 中所有元素和都互不相同，哈希表需要存储 n² 个键。

总结
这道题的核心技巧是“分组+哈希”，通过将四个数组分为两组，将问题转化为寻找两数之和的相反数。哈希表在这里的作用是高效地存储中间结果（前两组的和）并提供 O(1) 复杂度的查询，从而显著降低算法的时间复杂度。这是一种非常经典的用空间换取时间的策略。

哈希算法题目：四数之和 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亿次，效率极低，不可接受。因此，我们需要寻找更优的解法。核心思路：空间换时间我们可以将问题拆解。观察等式： nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0 。可以将其转化为： nums1[i] + nums2[j] = - (nums3[k] + nums4[l]) 。这个转化是解题的关键。它意味着，前两个数组的元素和，与后两个数组的元素和，互为相反数。引入哈希表基于上述思路，我们可以分两步走：第一步：遍历数组 nums1 和 nums2，计算所有可能的和 a + b ，并使用一个哈希表（在 Python 中通常用字典 dict ）来记录每个和出现的次数。第二步：遍历数组 nums3 和 nums4，计算所有可能的和 c + d ，然后查看哈希表中是否存在键 -(c + d) 。如果存在，那么就意味着我们找到了 (a+b) + (c+d) = 0 的组合。此时，将哈希表中 -(c + d) 对应的值（即该和出现的次数）累加到结果中。为什么是累加次数？因为对于某个特定的 -(c + d) ，它在哈希表中出现的次数，就等于在 nums1 和 nums2 中有多少种不同的 (i, j) 组合能组成这个和。详细步骤让我们通过一个微型例子来一步步验证。设： nums1 = [ 1, 2], nums2 = [ -1, -2], nums3 = [ -1, 2], nums4 = [ 0, 2 ]，n=2。步骤一：构建哈希表（处理前两个数组）初始化一个空字典 hash_map = {} ，用于存储和及其出现次数。遍历 nums1 和 nums2： i=0, j=0: 和 = 1 + (-1) = 0。 hash_map[0] 目前不存在，我们将其设为 1。 hash_map = {0: 1} i=0, j=1: 和 = 1 + (-2) = -1。 hash_map[-1] 不存在，设为 1。 hash_map = {0: 1, -1: 1} i=1, j=0: 和 = 2 + (-1) = 1。 hash_map[1] 不存在，设为 1。 hash_map = {0: 1, -1: 1, 1: 1} i=1, j=1: 和 = 2 + (-2) = 0。 hash_map[0] 已存在，将其值加 1，变为 2。 hash_map = {0: 2, -1: 1, 1: 1} 步骤二：统计结果（处理后两个数组）初始化结果计数器 count = 0 。遍历 nums3 和 nums4： k=0, l=0: 和 = (-1) + 0 = -1。我们需要找的键是 -(-1) = 1 。检查 hash_map ， 1 存在，其值为 1。所以 count += 1 ，现在 count = 1 。 k=0, l=1: 和 = (-1) + 2 = 1。我们需要找的键是 -(1) = -1 。检查 hash_map ， -1 存在，其值为 1。所以 count += 1 ，现在 count = 2 。 k=1, l=0: 和 = 2 + 0 = 2。我们需要找的键是 -(2) = -2 。检查 hash_map ， -2 不存在，跳过。 k=1, l=1: 和 = 2 + 2 = 4。我们需要找的键是 -(4) = -4 。检查 hash_map ， -4 不存在，跳过。最终结果 count = 2 。我们可以验证一下这两个元组： (i=0, j=0, k=0, l=1): 1 + (-1) + (-1) + 2 = (0) + (1) = 1? 不对。让我们仔细核对。实际上，根据我们的逻辑：第一个情况： hash_map[1]=1 对应 (i=1,j=0)，和 c+d=-1 对应 (k=0,l=0)。元组是 (1, 0, 0, 0)：nums1[ 1]=2, nums2[ 0]=-1, nums3[ 0]=-1, nums4[ 0 ]=0。和为 2 + (-1) + (-1) + 0 = 0。正确。第二个情况： hash_map[-1]=1 对应 (i=0,j=1)，和 c+d=1 对应 (k=0,l=1)。元组是 (0, 1, 0, 1)：nums1[ 0]=1, nums2[ 1]=-2, nums3[ 0]=-1, nums4[ 1 ]=2。和为 1 + (-2) + (-1) + 2 = 0。正确。复杂度分析时间复杂度：O(n²)。我们使用了两个独立的双重循环。第一个循环遍历 nums1 和 nums2，计算量为 n * n = n²。第二个循环遍历 nums3 和 nums4，计算量同样为 n²。总时间复杂度为 O(n²) + O(n²) = O(n²)，远优于最初的 O(n⁴)。空间复杂度：O(n²)。在最坏情况下，nums1 和 nums2 中所有元素和都互不相同，哈希表需要存储 n² 个键。总结这道题的核心技巧是“分组+哈希”，通过将四个数组分为两组，将问题转化为寻找两数之和的相反数。哈希表在这里的作用是高效地存储中间结果（前两组的和）并提供 O(1) 复杂度的查询，从而显著降低算法的时间复杂度。这是一种非常经典的用空间换取时间的策略。