数组与哈希中等1 种解法

#454四数相加 II

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

#数组#哈希表#分组

原题

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

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

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

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

提示：

n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-2²⁸ <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2²⁸

查看原题

解题主线

把四个数组分成两组，先统计 nums1 与 nums2 的所有两数和频次。
枚举 nums3 与 nums4 时查找其和的相反数，一次加入全部匹配组合数。
分组把四重枚举的 O(n⁴) 降为两个 O(n²) 阶段。

解法 1：两数组分组哈希

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

时间复杂度： O(n²)
空间复杂度： O(n²)

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