四数相加 II 图解题解
这道题到底在问什么
- 输入
- nums1=[1,2], nums2=[-2,-1], nums3=[-1,2], nums4=[0,2]
- 输出
- 2
先想最直接的笨办法
前两组枚举完，哈希表记下了所有 a+b 的和及次数：-1 出现 1 次，0 出现 2 次，1 出现 1 次。接下来查后两组。（动画第 13 步）
最优解：一步一步想明白
- 3记住「前两组的和入哈希,后两组查相反数」,下面每帧都在套它。
- 4左边四格:前两格是 nums1=[1,2]，后两格是 nums2=[−2,−1]。先把它们两两相加，结果存进右边哈希表。
- 5取 nums1 的 1（紫 i）和 nums2 的 -2（标 l），两数和 = -1。下一步把它记进哈希表。
- 6把和 -1 记进哈希表（高亮行），它现在出现了 1 次。继续下一对。
- 7取 nums1 的 1（紫 i）和 nums2 的 -1（标 l），两数和 = 0。下一步把它记进哈希表。
- 8把和 0 记进哈希表（高亮行），它现在出现了 1 次。继续下一对。
- 9取 nums1 的 2（紫 i）和 nums2 的 -2（标 l），两数和 = 0。下一步把它记进哈希表。
- 10把和 0 记进哈希表（高亮行），它现在出现了 2 次。继续下一对。
- 11取 nums1 的 2（紫 i）和 nums2 的 -1（标 l），两数和 = 1。下一步把它记进哈希表。
- 12把和 1 记进哈希表（高亮行），它现在出现了 1 次。继续下一对。
- 13前两组枚举完，哈希表记下了所有 a+b 的和及次数：-1 出现 1 次，0 出现 2 次，1 出现 1 次。接下来查后两组。
- 14左边四格换成：前两格 nums3=[−1,2]，后两格 nums4=[0,2]。哈希表不变（前两组的成果）。现在每对 (c,d) 去查相反数 −(c+d)。
- 15取 nums3 的 -1 和 nums4 的 0，和 = -1。要凑成 0，就得在哈希表里找 a+b = 1。
- 16哈希表里 1 出现了 1 次（高亮命中），说明有 1 组前两数能和它们配成 0，ans 加到 1。
- 17取 nums3 的 -1 和 nums4 的 2，和 = 1。要凑成 0，就得在哈希表里找 a+b = -1。
- 18哈希表里 -1 出现了 1 次（高亮命中），说明有 1 组前两数能和它们配成 0，ans 加到 2。
- 19取 nums3 的 2 和 nums4 的 0，和 = 2。要凑成 0，就得在哈希表里找 a+b = -2。
- 20哈希表里找不到 -2，这对配不出 0，ans 保持 2。
- 21取 nums3 的 2 和 nums4 的 2，和 = 4。要凑成 0，就得在哈希表里找 a+b = -4。
- 22哈希表里找不到 -4，这对配不出 0，ans 保持 2。
- 23后两组枚举完，累计 ans = 2，就是四数和为 0 的下标四元组个数。靠哈希表把 O(n⁴) 砍成了 O(n²)。
⚠️ 容易写错的地方
✗ 错：四重循环硬枚举
✓ 对：分两半 + 哈希,O(n²)
n=200 时 O(n⁴)=16 亿,O(n²)=4 万,差 4 万倍
✗ 错：哈希只存「是否出现」
✓ 对：要存「出现次数」
同一个和可能由多对 (a,b) 产生,次数都要累加进答案
✗ 错：查的时候算成 c+d
✓ 对：要查相反数 −(c+d)
目标是四数和为 0,即 a+b = −(c+d)
完整代码（Python / C++ / Java）
Python
from typing import List
from collections import Counter
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
count = Counter(a + b for a in nums1 for b in nums2)
return sum(count[-c - d] for c in nums3 for d in nums4)C++
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> count;
for (int a : nums1) for (int b : nums2) count[a + b]++;
int ans = 0;
for (int c : nums3) for (int d : nums4) if (count.count(-c - d)) ans += count[-c - d];
return ans;
}
};Java
import java.util.*;
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer,Integer> count = new HashMap<>();
for (int a : nums1) for (int b : nums2) count.put(a + b, count.getOrDefault(a + b, 0) + 1);
int ans = 0;
for (int c : nums3) for (int d : nums4) ans += count.getOrDefault(-c - d, 0);
return ans;
}
}复杂度
时间
O(n²)
两段各一个双重循环
空间
O(n²)
哈希表最多存 n² 个不同的和
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 四数相加 II 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么是「两两分组」而不是「三一分组」?+
两两分组让两边都是 O(n²):一边建哈希 O(n²)、另一边查哈希 O(n²),整体 O(n²) 且空间 O(n²)。三一分组(三数组建表)会变成 O(n³) 时间、O(n³) 空间,更差。均衡二分是最优。
和「两数之和 LC1」有什么关系?+
本质一样,都是「边枚举边查哈希里的目标补值」。LC1 是一维找 target−x;本题把「前两数组的和」当作一个整体 x、把 nums1×nums2 当作放大版的「数组」,再对「后两数组的和」找相反数,是 two-sum 思想在分组上的推广。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 四数相加 II 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。