LeetCode 454. 四数相加 II

约 4 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 阿里 拼多多 快手
标签
数组 哈希表

题目描述

✅ 454. 四数相加 II

image-20260928235640926

image-20260928235640927

题意分析

四个等长整数数组中各选择一个位置，统计满足四个元素之和为零的下标四元组数量。四个位置分别属于四个数组，彼此可以使用相同的下标编号，不存在同一数组元素被取两次的问题。

计数按下标组合区分。即使某些值相同、某些配对得到相同的和，它们来自不同位置时仍然是不同方案。需要返回方案总数，不是输出去重后的四个数值。

解法：两两分组哈希计数

核心思路

[!blue]

直接枚举四个下标需要四层循环。把等式改写为 a + b = -(c + d)，可以先把前两个数组的所有配对按和汇总，再用后两个数组的配对查互补值，把四项组合拆成两次二项枚举。

哈希表 sumCount[x] 保存前两个数组中和等于 x 的下标对数量。每枚举一个后半配对 (c, d)，它能与表中所有和为 -(c + d) 的前半配对组合，因此给答案增加该频次；没有互补记录就增加零。

这样既不漏计也不重复：任意合法四元组都有唯一的前半下标对和后半下标对，枚举到它的后半对时会被加入一次；不同前半对或后半对对应不同的四元组，本来就应分别计数。

如果某个互补的后半和也出现多次，每个后半下标对都会单独查表、累加一次前半频次，等价于将两组频次相乘。只保存和是否存在的集合，会丢掉前半配对的重数。

解题步骤

  1. 创建和到次数的哈希表。
  2. 遍历第一个数组的每个位置，与第二个数组所有位置配对，将对应和的次数加一。
  3. 遍历第三、第四数组的每个位置配对，计算两数和的相反数。
  4. 查表得到能够搭配它的前半下标对数量，全部累加到答案。
  5. 返回总数，不需要排序、去重或输出具体四元组。

代码实现

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> sumCount = new HashMap<>();

        for (int a : nums1) {
            for (int b : nums2) {
                int sum = a + b;

                // 统计下标对的次数，重复和不能去重
                sumCount.put(sum, sumCount.getOrDefault(sum, 0) + 1);
            }
        }

        int ans = 0;

        for (int c : nums3) {
            for (int d : nums4) {
                // 每个后半配对贡献所有互补前半配对
                ans += sumCount.getOrDefault(-(c + d), 0);
            }
        }

        return ans;
    }
}

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    sumCount := make(map[int]int)
    for _, a := range nums1 {
        for _, b := range nums2 {
            // 统计下标对的次数，重复和不能去重
            sumCount[a+b]++
        }
    }

    ans := 0
    for _, c := range nums3 {
        for _, d := range nums4 {
            // 每个后半配对贡献所有互补前半配对
            ans += sumCount[-(c + d)]
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：期望 $O(n^2)$，前后两组各枚举 n² 个配对，哈希插入与查询平均为 $O(1)$。
  • 空间复杂度：$O(n^2)$，前半两数和最多有 n² 种，重复和合并到同一个计数中。

关键点总结

[!green]

  • 用前后两组和的互补关系，替代逐个枚举所有四元组。
  • 哈希表记录下标对频次，保留重复值和重复和带来的独立方案。
  • 后半每个下标对单独贡献所有互补前半对，完整覆盖且不会重复一个四元组。
  • 不同数组间没有下标互异约束，不应套用单数组四数之和的去重逻辑。

易错点总结

[!yellow]

  • 使用集合而不是次数表，互补和出现多次时只能计算一部分方案。
  • 查找后半和本身，遗漏等式中的相反数，不能保证四项总和为零。
  • 每次找到互补值只给答案加一，忽略该值可能对应多个前半下标对。
  • 对数组值或两数和去重，改变按位置分别计数的题意。
  • 要求四个下标编号互不相同，给不同数组间的选择添加了不存在的限制。

相似题目

题目 难度 关联与区别
18. 四数之和 中等 四数目标相同，但本题从四个独立数组各选一个，可直接把两组两数和频次相乘。
1. 两数之和 简单 复用互补值查询，把单个元素替换为一组两数和，就能减少四层枚举。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/43663569
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！