#454. 四数相加 II

LeetCode 原题链接

#题目描述

给定四个长度相同的整数数组 nums1、nums2、nums3 和 nums4，计算有多少个下标四元组 (i, j, k, l) 满足：

nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0

示例：

输入：
nums1 = [1, 2]
nums2 = [-2, -1]
nums3 = [-1, 2]
nums4 = [0, 2]

输出：2

两个符合条件的下标组合对应：

1 + (-2) + (-1) + 2 = 0
2 + (-1) + (-1) + 0 = 0

#题型判断

最直接的思路是使用四层循环，枚举四个数组中的所有组合：

for (const a of nums1) {
  for (const b of nums2) {
    for (const c of nums3) {
      for (const d of nums4) {
        if (a + b + c + d === 0) {
          count++;
        }
      }
    }
  }
}

如果每个数组的长度都是 n，这种做法需要 O(n⁴) 时间，数据稍大就会超时。

观察等式：

a + b + c + d = 0

可以把它拆成：

a + b = -(c + d)

也就是说，只要知道前两个数组的和出现过多少次，就能快速判断后两个数组的和能与多少种前半组合配对。

这是一种常见的“分组 + 哈希表”降维思路，也叫折半枚举。

#核心思路

算法分为两步。

#第一步：统计 nums1 和 nums2 的两数之和

枚举 nums1 和 nums2 的所有组合，用哈希表记录每个和出现的次数：

sumCount[sum] = nums1 与 nums2 中，两数之和为 sum 的组合数量

注意，哈希表保存的是出现次数，而不是只记录某个和是否存在。因为题目要求的是下标组合数量，相同的和可能来自多个不同下标。

#第二步：枚举 nums3 和 nums4

对于每一组 c + d，要使四数之和为 0，前两个数的和必须是：

target = -(c + d)

如果 target 在哈希表中出现了 x 次，那么当前的 (c, d) 就能与前面的 x 组 (a, b) 配对，所以答案增加 x。

#示例推演

仍以示例为例：

nums1 = [1, 2]
nums2 = [-2, -1]

枚举前两个数组：

最终哈希表表示：

-1 出现 1 次
 0 出现 2 次
 1 出现 1 次

再枚举后两个数组：

nums3 = [-1, 2]
nums4 = [0, 2]

所以最终答案是 2。

#JavaScript 实现

var fourSumCount = function (nums1, nums2, nums3, nums4) {
  // key：nums1 与 nums2 中两个数的和
  // value：这个和由多少组下标产生
  const sumCount = new Map();

  // 统计前两个数组的所有两数之和
  for (const a of nums1) {
    for (const b of nums2) {
      const sum = a + b;
      sumCount.set(sum, (sumCount.get(sum) || 0) + 1);
    }
  }

  let result = 0;

  // 枚举后两个数组，寻找与 c + d 互为相反数的前半和
  for (const c of nums3) {
    for (const d of nums4) {
      const target = -(c + d);

      // target 不存在时，Map.get 返回 undefined，用 0 代替
      result += sumCount.get(target) || 0;
    }
  }

  return result;
};

#为什么 Map 中必须保存次数？

考虑下面的输入：

nums1 = [0, 0]
nums2 = [0, 0]
nums3 = [0]
nums4 = [0]

nums1 与 nums2 可以组成四组下标：

(0, 0)、(0, 1)、(1, 0)、(1, 1)

它们的和都是 0，所以哈希表中应该保存：

sumCount.get(0) === 4

后两个数组只有一组 (0, 0)，但它可以与前面的四组分别配对，因此答案是 4。如果哈希表只保存 true 或只保存一次 0，就会漏掉重复值产生的合法下标组合。

#正确性说明

对于任意一个后半组合 (c, d)，四数之和为零当且仅当前半组合满足：

a + b = -(c + d)

第一阶段已经统计了每个前半和对应的全部 (a, b) 组合数量。第二阶段枚举每一个 (c, d)，并把所有能与它配对的前半组合数量加入答案。

因此：

• 每个合法四元组一定会在枚举它的 (c, d) 时被统计，不会遗漏。
• 每个四元组只对应唯一的一组 (a, b) 和 (c, d)，不会重复统计。

所以算法返回的正是满足条件的下标四元组数量。

#复杂度分析

假设四个数组的长度都是 n：

• 时间复杂度：O(n²)。前两个数组和后两个数组分别进行一次双层枚举。
• 空间复杂度：O(n²)。最坏情况下，前两个数组产生的 n² 个和都不同。

相较于暴力枚举的 O(n⁴)，该方案用额外空间把时间复杂度降低到了 O(n²)。

如果四个数组长度不同，时间复杂度更准确地写作：

O(nums1.length × nums2.length + nums3.length × nums4.length)

#与“三数之和、四数之和”的区别

这道题与 LeetCode 15、18 不同：

• 本题从四个不同数组中各选一个元素，求的是下标组合数量。
• 不需要返回具体组合，也不需要去重。
• 输入数组不必排序，哈希计数更合适。
• 相同的数值只要来自不同下标，就属于不同组合，必须分别计数。

#易错点

• 使用四层循环，导致 O(n⁴) 超时。
• 哈希表只记录某个和是否存在，没有记录出现次数。
• 查找的是 c + d，而不是它的相反数 -(c + d)。
• 看到重复值就去重。本题统计下标四元组，重复元素可能产生不同的合法组合。
• 使用 if (sumCount.get(target)) 判断是否存在。虽然本题计数一定为正，这样可以运行，但使用 sumCount.get(target) || 0 直接累加更简洁。
• 把本题误当作一个数组中的“四数之和”，进行排序和双指针去重。

#面试时怎么说

暴力枚举四个数组需要 O(n⁴)。把等式拆成 a + b = -(c + d)，先用哈希表统计前两个数组的所有两数之和及出现次数，再枚举后两个数组，每次查找相反数出现了多少次并累加。这样时间复杂度降为 O(n²)，空间复杂度为 O(n²)。哈希表必须保存次数，因为题目统计的是下标组合，而不是不同的数值组合。

#自测

1. 为什么可以把四个数组拆成两组？
2. 哈希表的 key 和 value 分别表示什么？
3. 为什么不能只用 Set 记录两数之和？
4. 本题遇到重复元素时为什么不能去重？