从454. 四数相加 II 中学到Counter，我们使用哈希表（Counter）将时间复杂度从暴力的 (O(n^4)) 优化到 (O(n^2))。
一、Counter的内部数据结构
✅Counter是什么？
Counter是 Python 标准库collections模块中的一个字典子类（dict subclass）。- 它专门用于计数可哈希对象。
- 底层实现就是哈希表（hash table），和普通
dict一样，基于开放寻址或链地址法（CPython 中是开放寻址）。
🔧 内部结构示例
from collections import Counter cnt = Counter(['a', 'b', 'a', 'c', 'b', 'a']) print(cnt) # 输出: Counter({'a': 3, 'b': 2, 'c': 1})其内部存储等价于：
{'a': 3, 'b': 2, 'c': 1}- 键（key）：元素（必须可哈希，如 int、str、tuple）
- 值（value）：该元素出现的次数（int）
💡 所以
Counter的插入、查询、更新操作平均时间复杂度都是O(1)。
二、code 中Counter的实例分析
cnt = Counter(x + y for x in nums1 for y in nums2)📌 这行做了什么？
- 遍历
nums1和nums2的所有组合（共 (n^2) 对） - 计算每对的和
s = x + y - 统计每个和
s出现的次数
🧪 举个具体例子
假设：
nums1 = [1, 2] nums2 = [-2, -1]那么x + y的所有可能为：
- 1 + (-2) = -1
- 1 + (-1) = 0
- 2 + (-2) = 0
- 2 + (-1) = 1
所以：
cnt = Counter({0: 2, -1: 1, 1: 1})即：
cnt[-1] == 1 cnt[0] == 2 cnt[1] == 1 cnt[999] == 0 # 不存在的键返回 0（这是 Counter 的特性！）✅ 关键优势：访问不存在的键不会报错，而是返回 0，这正是你代码中
cnt[-x-y]安全的原因！
三、完整执行流程示例
输入：
nums1 = [1, 2] nums2 = [-2, -1] nums3 = [-1, 2] nums4 = [0, 2]目标：找满足a + b + c + d == 0的元组数量。
Step 1: 构建cnt（a + b 的频次）
a+b: 1 + (-2) = -1 1 + (-1) = 0 2 + (-2) = 0 2 + (-1) = 1 cnt = {-1:1, 0:2, 1:1}Step 2: 遍历c + d，查- (c + d)是否在cnt中
c+d: -1 + 0 = -1 → 需要 a+b = 1 → cnt[1] = 1 -1 + 2 = 1 → 需要 a+b = -1 → cnt[-1] = 1 2 + 0 = 2 → 需要 a+b = -2 → cnt[-2] = 0 2 + 2 = 4 → 需要 a+b = -4 → cnt[-4] = 0 总和 = 1 + 1 + 0 + 0 = 2✅ 返回2，正确。
四、为什么用Counter而不是普通dict？
你可以用普通dict，但需要手动处理默认值：
# 手动写法（不推荐） d = {} for x in nums1: for y in nums2: d[x+y] = d.get(x+y, 0) + 1 total = 0 for x in nums3: for y in nums4: total += d.get(-(x+y), 0)而Counter自动处理缺失键为 0，代码更简洁安全：
# 你的写法（推荐） cnt = Counter(x+y for x in nums1 for y in nums2) return sum(cnt[-x-y] for x in nums3 for y in nums4)✅ 这正是
Counter在此场景下的最大价值！
五、复杂度分析
| 步骤 | 时间 | 空间 |
|---|---|---|
构建cnt | (O(n^2)) | (O(n^2))（最坏所有和都不同） |
遍历nums3+nums4 | (O(n^2)) | (O(1)) |
| 总计 | (O(n^2)) | (O(n^2)) |
远优于暴力 (O(n^4))。
总结
Counter是基于哈希表的字典子类，用于计数。- 在你的代码中，它存储了
nums1 + nums2所有可能和的出现次数。 - 利用
Counter访问不存在键返回 0的特性，使得cnt[-x-y]安全且简洁。 - 整体算法是空间换时间的典型应用，将四重循环降为两个双重循环。
)
