454. 四数相加 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

数据范围：

• n == nums1.length == nums2.length == nums3.length == nums4.length
• 1 <= n <= 200
• -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

示例

示例 1：

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

• (0, 0, 0, 1) → 1 + (-2) + (-1) + 2 = 0
• (1, 1, 0, 0) → 2 + (-1) + (-1) + 0 = 0

示例 2：

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

核心思路

朴素做法：四重循环枚举所有 (i, j, k, l)，时间 $O(n^4)$。当 n = 200 时是 $1.6 \times 10^9$，会超时。

分组思路：把四个数组分成两组：

• 第一组：nums1 + nums2，共 n² 种和；
• 第二组：nums3 + nums4，共 n² 种和。

问题转化为：从两组和中各选一个，使它们的和等于 0，求方案数。

哈希表优化：

1. 遍历 nums1 和 nums2，用哈希表记录每个和出现的次数；
2. 遍历 nums3 和 nums4，对每个和 s，在哈希表中查询 -s 出现的次数，累加到答案。

时间复杂度从 $O(n^4)$ 降到 $O(n^2)$。

关键点：为什么不能像「两数之和」那样用双指针？因为本题求的是方案数，需要统计每个和的出现次数，而哈希表天然支持计数。

---

方法：分组 + 哈希表

思路及解法

1. 创建一个哈希表 count，键为「nums1[i] + nums2[j] 的和」，值为该和出现的次数；
2. 用两重循环遍历 nums1 和 nums2，把所有可能的和存入哈希表；
3. 初始化答案 ans = 0；
4. 用两重循环遍历 nums3 和 nums4，对每个和 s：
   • 若 -s 在哈希表中，ans += count[-s]；
5. 返回 ans。

为什么这样做是对的：

对于每个 (k, l) 组合，nums3[k] + nums4[l] = s。要让总和为 0，需要 nums1[i] + nums2[j] = -s。哈希表里已经统计了所有 (i, j) 组合中「和为 -s」的数量，直接加上即可。

代码

from collections import defaultdict

class Solution:
    def fourSumCount(self, nums1: list[int], nums2: list[int], nums3: list[int], nums4: list[int]) -> int:
        count = defaultdict(int)

        # 第一组：nums1 + nums2
        for a in nums1:
            for b in nums2:
                count[a + b] += 1

        ans = 0
        # 第二组：nums3 + nums4
        for c in nums3:
            for d in nums4:
                ans += count[-c - d]

        return ans

defaultdict(int) 在不存在的键上返回 0，省去 if 判断。

复杂度分析

• 时间复杂度：$O(n^2)$，两组各遍历 n² 次，哈希表操作 $O(1)$。
• 空间复杂度：$O(n^2)$，哈希表最坏存储 n² 个不同的和。

---

关键细节

1. 为什么分组是 (1,2) 和 (3,4) 而不是其他分法

其实任意两两分组都可以：

• (1,2) + (3,4)；
• (1,3) + (2,4)；
• (1,4) + (2,3)。

分组只是为了让每组内部两两求和，把四重循环拆成两次二重循环。本题没有强制要求元组顺序，所以哪种分组都行。

2. 为什么不用双指针

双指针适用于「求一组满足条件的元素」，前提是数组有序。本题是四个数组、求方案数，且无法直接排序（会丢失下标对应关系）。所以用哈希表计数更合适。

3. 哈希表的值是「次数」而不是「是否存在」

题目要求的是元组数量，而不是「是否存在」。所以哈希表要记录每个和的出现次数，查询时累加次数而不是加 1。

反例：如果哈希表只存布尔值（存在性），那么对于多个 (i, j) 得到相同和的情况，会少算方案数。

4. 负数处理

和可能为负，-s 也可能为负。Python 的字典键可以是任意整数，defaultdict(int) 处理负数也没问题。

5. 溢出问题

题目数据 |nums[i]| <= 2^28，四个数相加最大约 $2^{30}$，在 32 位整数范围内（int 上限约 $2^{31}$），Python 无溢出问题。C++ 用 long long 更保险。

6. 与 LC 1（两数之和）的对比

	LC 1 两数之和	LC 454 四数相加 II
目标	找一对下标，和为 target	统计所有四元组，和为 0
方法	哈希表存「值 → 下标」	哈希表存「和 → 次数」
输出	一组下标	方案数
时间	$O(n)$	$O(n^2)$

核心思想一致：用哈希表把「查找」从 $O(n)$ 降到 $O(1)$。

---

总结

• 核心思路：四数之和 → 两数之和 + 两数之和；
• 分组：(nums1, nums2) 和 (nums3, nums4) 各生成 n² 个和；
• 哈希表：
  • 第一组：记录「和 → 出现次数」；
  • 第二组：对每个和 s，查询 -s 的次数并累加；
• 时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$；
• 通用套路：多数组求和 → 分组 + 哈希表，把高次枚举拆成两次低次枚举。

相关题目

• LC 1. 两数之和（哈希表经典）
• LC 18. 四数之和（一个数组内，排序 + 双指针）
• LC 15. 三数之和（排序 + 双指针）
• LC 167. 两数之和 II - 输入有序数组（双指针）