​从454. 四数相加 II 中学到Counter​

从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在此场景下的最大价值！

五、复杂度分析

远优于暴力 (O(n^4))。

总结

• Counter是基于哈希表的字典子类，用于计数。
• 在你的代码中，它存储了nums1 + nums2所有可能和的出现次数。
• 利用Counter访问不存在键返回 0的特性，使得cnt[-x-y]安全且简洁。
• 整体算法是空间换时间的典型应用，将四重循环降为两个双重循环。