454. 四数相加 II

题目

力扣题目

给定四个长度均为 n 的整数数组 nums1、nums2、nums3、nums4，计算满足下式的下标元组 (i, j, k, l) 数量：

示例 1：

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

输出：2

示例 2：

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

提示：

• 四个数组长度相同
• 1 <= n <= 200
• -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

考察内容

• 将四数组拆分为两个二数组问题
• 使用哈希表统计两数之和的频率
• 补数思想
• 重复元素与组合数量
• 从 $O(n^4)$ 优化到 $O(n^2)$

解题思路

分成两组

四重循环可以枚举所有下标元组，但时间复杂度为 $O(n^4)$。将等式重新整理：

先枚举 nums1 和 nums2 的所有组合，用哈希表 count 记录每个两数之和出现了多少次。再枚举 nums3 和 nums4，若它们的和为 sumCD，就在哈希表中查找补数 -sumCD。

这里哈希表的值必须是出现次数，不能只记录是否存在。不同下标组合即使得到相同的两数之和，也都应计入答案。

样例过程

对于 nums1 = [1,2]、nums2 = [-2,-1]：

再枚举 nums3 = [-1,2]、nums4 = [0,2]：

• -1 + 0 = -1，需要补数 1，哈希表中出现 1 次；
• -1 + 2 = 1，需要补数 -1，哈希表中出现 1 次；
• 其余组合需要的补数不存在。

最终答案为 1 + 1 = 2。

共枚举两次 $n^2$ 个二元组：

• 时间复杂度：$O(n^2)$，基于哈希操作平均 $O(1)$
• 空间复杂度：$O(n^2)$，最坏需要保存所有不同的两数之和

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

本题统计的是来自四个独立数组的下标元组数量，不要求输出不重复的数值组合，因此无需排序和双指针去重。相同和值出现多少次，必须完整保留其频率。

代码演示

int fourSumCount(const std::vector<int>& nums1,
                 const std::vector<int>& nums2,
                 const std::vector<int>& nums3,
                 const std::vector<int>& nums4) {
    std::unordered_map<int, int> pairCount;

    for (int a : nums1) {
        for (int b : nums2) {
            ++pairCount[a + b];
        }
    }

    int result = 0;

    for (int c : nums3) {
        for (int d : nums4) {
            auto it = pairCount.find(-(c + d));
            if (it != pairCount.end()) {
                result += it->second;
            }
        }
    }

    return result;
}

易错点

• 使用集合代替频率表：集合会丢失相同和值的出现次数，导致少计下标组合。
• 查找 c + d 而不是补数：需要查找的是 -(c + d)。
• 找到补数后只加 1：应加上 pairCount[补数]，因为该和值可能由多组 (i,j) 得到。
• 使用四重循环：时间复杂度为 $O(n^4)$，无法利用问题的可分组结构。
• 照搬三数之和的去重逻辑：本题统计下标元组，重复数值形成的不同下标组合必须保留。
• 误以为必须固定前两个数组分组：任意把四个数组分成两组都可以，复杂度相同。

总结

四数相加 II 的核心是“分组 + 补数”：先把两个数组的所有和值压缩到一张频率表中，再用另外两个数组的和值查找相反数。频率表不仅用于判断存在性，还保存每种和值贡献的组合数量。

相关题目

• 1. 两数之和
• 15. 三数之和
• 18. 四数之和
• 560. 和为 K 的子数组