What is the main pattern used in 4Sum II?

The main pattern is array scanning combined with hash map lookups to store partial sums for efficient complement checks.

Why not use four nested loops for this problem?

Four nested loops have O(n^4) time complexity, which is inefficient. Using pair sums and hash lookups reduces it to O(n^2).

How do hash maps help in counting quadruples?

They store frequencies of sums from the first two arrays, allowing constant-time checks for complementary sums from the last two arrays.

Can this method be extended to k-sum problems?

Yes, the hash map pair-sum strategy generalizes to k-sum by splitting arrays and storing partial sums efficiently.

What common mistake occurs with negative numbers?

Forgetting to negate the second pair sum when checking the hash map can cause incorrect counts of valid quadruples.

#454

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

四数相加 II

给你四个整数数组 nums1 、 nums2 、 nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足： 0 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 示例 1：输入： nums1 = [1,2…

数组哈希表

题目描述

给你四个整数数组 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²⁸

lightbulb

解题思路

方法一：哈希表

我们可以将数组 $nums1$ 和 $nums2$ 中的元素 $a$ 和 $b$ 相加，将所有可能的和存储在哈希表 $cnt$ 中，其中键为两数之和，值为两数之和出现的次数。

然后我们遍历数组 $nums3$ 和 $nums4$ 中的元素 $c$ 和 $d$ ，令 $c+d$ 为目标值，那么答案即为 $cnt[-(c+d)]$ 的累加和。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ ，其中 $n$ 是数组的长度。

1

2

3

4

5

6

7

class Solution:
    def fourSumCount(
        self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]
    ) -> int:
        cnt = Counter(a + b for a in nums1 for b in nums2)
        return sum(cnt[-(c + d)] for c in nums3 for d in nums4)

speed

复杂度分析

指标	值
时间	complexity is O(n^2) for computing pair sums and lookups, instead of O(n^4). Space complexity is O(n^2) to store hash map frequencies of the first two arrays' sums.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Mentions using pair sums to reduce brute-force iterations.
question_mark
Checks if candidates from remaining arrays complement existing sums.
question_mark
Looks for efficient O(n^2) approach instead of O(n^4).

warning

常见陷阱

外企场景

error
Forgetting negative values when computing complements leads to wrong counts.
error
Double-counting pairs by not using hash map frequencies correctly.
error
Attempting a naive four-loop approach causing TLE for larger n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Three-sum or k-sum problems with similar pair-sum hash patterns.
arrow_right_alt
Finding tuples with product equal to a target instead of sum.
arrow_right_alt
Using sorted arrays with two-pointer approaches instead of hash maps.

help

常见问题

外企场景

继续练习

#457 环形数组是否存在循环 #448 找到所有数组中消失的数字 #447 回旋镖的数量