数组与哈希中等1 种解法

#454四数相加 II

从四个等长数组各选一个元素，统计四数之和为 0 的下标元组数量。

#数组#哈希表#分组

解题主线

把四个数组分成两组，先统计 nums1 与 nums2 的所有两数和频次。

枚举 nums3 与 nums4 时查找其和的相反数，一次加入全部匹配组合数。

分组把四重枚举的 O(n⁴) 降为两个 O(n²) 阶段。

解法 1：两数组分组哈希

记录前两个数组的两数和频次，再枚举后两个数组并累加互为相反数的频次。

时间复杂度

O(n²)

空间复杂度

O(n²)

454. 四数相加 II · 两数组分组哈希

java

import java.util.HashMap;
import java.util.Map;

final class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> pairFrequencies = new HashMap<>();
        for (int first : nums1) {
            for (int second : nums2) {
                pairFrequencies.merge(first + second, 1, Integer::sum);
            }
        }

        int tuples = 0;
        for (int third : nums3) {
            for (int fourth : nums4) {
                tuples += pairFrequencies.getOrDefault(-third - fourth, 0);
            }
        }
        return tuples;
    }
}

记录前两个数组的两数和频次，再枚举后两个数组并累加互为相反数的频次。

边界与易错点

哈希表存的是两数和出现次数，不是只记录是否出现。
计数针对下标元组，数组中重复值产生的不同下标组合都要统计。
LeetCode 约束保证最终答案在 int 范围内。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q454_fourSumCount.java