LeetCode 454. 四数相加 II

Categories:

题目描述
思路分析
1. 解法一：哈希统计两数之和（推荐）
相似题目

题目描述

✅ 454. 四数相加 II

思路分析

解法一：哈希统计两数之和（推荐）

核心思路：

先统计 A + B 的所有和及其出现次数。

再遍历 C + D，累加 -(c + d) 在哈希表中的计数。

总计数即为满足条件的四元组数量。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示数组长度。

空间复杂度：O(n^2)，哈希表存储所有两数组和。

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

        // 统计 A + B 的所有和
        for (int a : nums1) {
            for (int b : nums2) {
                map.put(a + b, map.getOrDefault(a + b, 0) + 1);
            }
        }

        int res = 0;

        // 查找 -(C + D)
        for (int c : nums3) {
            for (int d : nums4) {
                res += map.getOrDefault(-(c + d), 0);
            }
        }

        return res;
    }
}

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
	cnt := make(map[int]int)

	// 统计 A + B 的所有和
	for _, a := range nums1 {
		for _, b := range nums2 {
			cnt[a+b]++
		}
	}

	res := 0

	// 查找 -(C + D)
	for _, c := range nums3 {
		for _, d := range nums4 {
			res += cnt[-(c + d)]
		}
	}

	return res
}

相似题目

题目	难度	考察点
1. 两数之和	简单	哈希表
15. 三数之和	中等	双指针
18. 四数之和	中等	排序 + 双指针
454. 四数相加 II	中等	哈希表
560. 和为 K 的子数组	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/43663569