前缀、差分与哈希状态 · HTML
数学 / 逻辑形态
构造 count[x]=|{i:a[i]=x}|。后续答案只通过键与频次计算；消费一个实例时 decrement，归零时可删除键。
识别信号
- 顺序不重要，答案只依赖每个值出现多少次。
- 需要比较两个多重集合。
- 值域有限或不同键数量远小于 n。
- 要找互补值、最高频、唯一值或按频率重建。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 相邻顺序决定答案 | 频次会丢失位置和排列信息，不能处理依赖顺序的模式。 |
| 巨大稠密数组值域 | 不要按最大值开超大数组；用哈希或坐标压缩。 |
核心不变量
处理扫描前缀后，count[x] 精确等于其中 x 的出现次数；所有频次非负，其总和等于已计入元素数减已消费数。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | key→count 的数组/字典，可选的 distinct、最大频次或桶。 |
| Transition | 读入 x 时 count[x]+=1；匹配/消费时在验证正频次后减 1，必要时删除零键。 |
| Frontier / order | 已扫描元素被压缩成频次表；键域而不是输入索引成为后续遍历前沿。 |
Python 骨架
def multiset_equal(left, right):
if len(left) != len(right):
return False
count = {}
for value in left:
count[value] = count.get(value, 0) + 1
for value in right:
remaining = count.get(value, 0)
if remaining == 0:
return False
if remaining == 1:
del count[value]
else:
count[value] = remaining - 1
return not count
正确性思路
- 第一遍后 count 是 left 多重集合的精确表示。
- 第二遍每个 right 元素必须消费一个同值实例；缺少实例时立即证明不等。
- 等长且所有消费完成后表为空，当且仅当两侧每个键频次相同。
复杂度
| Time | Space | Parameters |
|---|
| 期望 O(n+m) | O(k) | n、m 为输入长度，k 为不同键数；有限小值域数组计数可给确定 O(1) 访问。 |
边界条件
- 空输入的频次表为空。
- 键可为负数或复合可哈希对象时使用 dict。
- 重复消费前必须确认频次大于 0。
- 浮点值作为键需谨慎精度与 NaN 语义。
错误模式
| Pattern | Why it fails / fix |
|---|
| 使用 set 丢掉重数 | {a,a,b} 与 {a,b,b} 的 set 相同但多重集合不同。 |
| 归零键不删除却用 len(count) | 若 distinct 依赖字典长度，零频键必须删除。 |
| 按值域开不可控数组 | max-min 巨大时空间爆炸，应改哈希。 |
选择与排除规则
- 只依赖出现次数：先画 frequency map。
- 键域小且连续：数组通常更快；否则 dict。
- 还依赖原位置：频次只能作辅助，不能替代索引状态。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 两者多重集合相等，尽管顺序不同。 |
| Setup | 比较 [r,r,s] 与 [s,r,r]。 |
| Trace | 左表 {r:2,s:1}；右侧依次消费后为空。 |
Recall prompts
我的补充