LeetCode LCR 066. 键值映射

约 8 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
字符串 哈希表 LCR 设计 字典树
目录

题目描述

✅ LCR 066. 键值映射

题意分析

设计一个映射结构，支持两个操作：insert(key, val) 写入一个键值对，sum(prefix) 返回所有以该前缀开头的键所对应的值之和。

insert 的语义是覆盖而不是累加：同一个键被插入两次时，新值直接替换旧值，而不是把两个值加起来。这一条决定了实现里必须能拿到「这个键上一次的值」，否则无法把旧的影响撤销掉。

sum 求的是「前缀」而非「整键」的聚合。空前缀不会被查询，但前缀可以等于某个完整的键，此时该键也计入求和——「以 apple 为前缀」包含 apple 自己。

约束是键长与前缀长都不超过 50，调用总次数不超过 50。规模小到几乎可以随便写，真正被考察的是设计取舍：是把开销放在写入侧还是查询侧。

边界上要注意三处：查询的前缀可能没有任何键匹配，此时返回 0 而不是报错；同一个键被反复覆盖时，历史值不能残留；值可以是任意正整数，累加时按题目范围不会溢出，但覆盖时的增量可能是负数。

解法：哈希表统计状态

核心思路

最直接的实现是拿一个哈希表存全部键值对，sum 时遍历所有键、逐个判断是不是以给定前缀开头，命中就累加。写入 $O(1)$，查询 $O(N \cdot P)$。正确，但把全部代价压在了查询侧。

瓶颈在于查询时做了大量注定失败的前缀比较：绝大多数键与查询前缀连第一个字符都不同，却仍要被取出来比一次。而「以某前缀开头的键之和」这个量，其实在写入的那一刻就已经可以确定它会影响哪些前缀。

观察到：一个长度为 $L$ 的键，它只会影响自己的 $L$ 个前缀的答案，一个都不多。既然前缀的数量这么少且完全枚举得起，就可以把聚合结果预先摊到每个前缀上，让查询退化成一次直接读表。

由此定下两张表的状态定义：t[key] 表示键 key 当前的值，data[p] 表示「所有以 p 为前缀的键的值之和」。查询时 sum(prefix) 就是 data[prefix]，读一次即可，缺失则为 0。

写入的难点在于覆盖语义。若直接给每个前缀加上新值，旧值的贡献就永远留在表里了。正确做法是先取出旧值 old（不存在则为 0），算出增量 val - old，再把这个增量加到 $L$ 个前缀上，同时更新 t[key] = val。增量可正可负，负增量正好抵消掉旧值多算的部分。

维持的不变量是：任何时刻，data[p] 恒等于「当前所有以 p 开头的键的 t 值之和」。每次写入只改动一个键，因此只需沿着它的 $L$ 个前缀施加一次差分修正，就能让不变量继续成立。

解题步骤

  • 建两张哈希表：t 记录键到当前值的映射，data 记录前缀到聚合和的映射。两张表缺一不可——data 用于回答查询，t 用于在覆盖时算出增量。
  • insert 先从 t 中取出该键的旧值，键不存在时取 0。取旧值必须发生在写入新值之前，顺序反了就永远拿到新值、增量恒为 0。
  • 把 t[key] 更新为 val，完成对键本身的记录。
  • 令前缀长度从 1 递增到键长，对每个前缀执行 data[前缀] += val - old。从 1 开始是因为空前缀不会被查询；上界取到键长本身，是因为「前缀等于整个键」也是合法查询。
  • 施加的是增量 val - old 而不是 val。这一步是覆盖语义的全部实现：首次插入时 old 为 0，增量等于 val；重复插入时增量自动扣掉了旧的贡献。
  • sum 直接返回 data[prefix]，缺失时返回 0。不需要任何遍历或比较，查询代价只有一次哈希。

以 insert("apple", 3) → sum("ap") → insert("app", 2) → sum("ap") → insert("apple", 5) → sum("apple") 走一遍：第一次插入时 old = 0、增量 3，五个前缀 a、ap、app、appl、apple 的 data 各加 3，t = {apple: 3}。sum("ap") 读到 3。插入 ("app", 2) 时 old = 0、增量 2，三个前缀 a、ap、app 各加 2，此时 data["ap"] = 5、data["app"] = 5、data["appl"] = 3，t = {apple: 3, app: 2}。sum("ap") 读到 5，正确——两个键都以 ap 开头。再插入 ("apple", 5)：旧值 old = 3，增量为 5 - 3 = 2，五个前缀各加 2，data["a"] 从 5 变 7、data["ap"] 变 7、data["app"] 变 7、data["appl"] 从 3 变 5、data["apple"] 从 3 变 5。sum("apple") 读到 5，正是覆盖后的新值，而不是 3 与 5 累加出的 8。

代码实现

class MapSum {
    private Map<String, Integer> data;
    private Map<String, Integer> t;

    public MapSum() {
        data = new HashMap<>();
        t = new HashMap<>();
    }

    public void insert(String key, int val) {
        int old = t.getOrDefault(key, 0);
        t.put(key, val);
        for (int i = 1; i < key.length() + 1; ++i) {
            String k = key.substring(0, i);
            data.put(k, data.getOrDefault(k, 0) + (val - old));
        }
    }

    public int sum(String prefix) {
        return data.getOrDefault(prefix, 0);
    }
}

type MapSum struct {
    data map[string]int
    t    map[string]int
}

func Constructor() MapSum {
    return MapSum{
        data: make(map[string]int),
        t:    make(map[string]int),
    }
}

func (this *MapSum) Insert(key string, val int) {
    old := this.t[key]
    this.t[key] = val
    for i := 1; i < len(key)+1; i++ {
        k := key[:i]
        this.data[k] += (val - old)
    }
}

func (this *MapSum) Sum(prefix string) int {
    return this.data[prefix]
}

复杂度分析

  • 时间复杂度：insert 为 $O(L^2)$，需要枚举 $L$ 个前缀、每个前缀的取子串与哈希各 $O(L)$；sum 为 $O(P)$，只有一次哈希查表的代价，与已插入的键数量无关。
  • 空间复杂度：$O(N \cdot L^2)$ 的上界，最坏情况下 $N$ 个键各自贡献 $L$ 个互不相同、长度至多 $L$ 的前缀；共享前缀的键会合并计费，实际远小于该上界。

关键点总结

  • 「查询要的聚合值，在写入时就能确定影响范围」是把代价从查询侧搬到写入侧的信号。当影响范围小（这里只有 $L$ 个前缀）而查询频繁时，预摊总是划算的。
  • 覆盖语义必须靠「旧值 + 增量」实现。凡是聚合结构支持更新而非只追加，都要先想清楚如何撤销旧贡献，这是可迁移的差分思想。
  • 取旧值一定要在写新值之前。这类顺序依赖是设计题里最隐蔽的 bug 来源，写代码时把「读旧 → 算增量 → 写新 → 传播」固定成四步能避免。
  • 两张表各司其职：一张回答查询，一张支撑更新。不要试图用一张表兼顾，否则要么无法覆盖、要么查询退化成遍历。
  • 前缀范围取 [1, L] 闭区间，因为「前缀等于整键」是合法查询。区间端点的取舍要直接对照题目语义确认，不要凭习惯写 < L。
  • 面试视角：这题的标准答案是 Trie——节点上挂一个 val 字段表示子树和，insert 沿路径把增量加到每个节点，sum 走到前缀终点直接读值，insert 与 sum 都降到 $O(L)$。用哈希实现要主动说明「因为约束里长度只有 50，$O(L^2)$ 完全够用，若长度放大到 $10^4$ 就该换 Trie」，把取舍讲透。
  • 面试视角：常见追问是「如果还要支持删除键怎么办」。答删除等价于 insert(key, 0)，同一套增量传播机制直接复用，这也正是差分设计的好处。

易错点总结

  • 错误写法：直接 data[前缀] += val，不扣旧值。用例 insert("a", 3)、insert("a", 2)、sum("a") → 返回 5，正确答案是 2，insert 是覆盖不是累加。
  • 错误写法：先写 t[key] = val 再读 old。用例 insert("a", 3)、insert("a", 2)、sum("a") → old 读成了新值 2，增量恒为 0，第二次插入完全没生效，返回 3，正确答案是 2。
  • 错误写法：前缀长度上界写成 i < key.length()。用例 insert("apple", 3)、sum("apple") → 最长只更新到 "appl"，data["apple"] 从未被写入，返回 0，正确答案是 3。
  • 错误写法：前缀长度从 0 开始。用例 任意插入 → 空串键被写入 data，虽然题目不查询空前缀，但每次插入多做一轮无意义的写表；若实现中把空串误当作有效前缀参与查询，还会返回全局和。
  • 错误写法：sum 时遍历 data 的所有键做前缀匹配。用例 insert("apple", 3)、sum("ap") → 结果虽对，但把 data 的语义从「前缀聚合」误用成「键集合」，一旦键数增大就退化成 $O(N \cdot P)$，预摊的意义完全丧失。
  • 错误写法：只用一张 data 表，不额外记录 t。用例 insert("a", 3)、insert("a", 2) → 无处取旧值，只能选择累加或全量重建，前者结果错、后者复杂度退化。
  • 错误写法：sum 对缺失的前缀直接取值而不给默认 0（Java 用 get 而非 getOrDefault）。用例 insert("apple", 3)、sum("b") → 返回 null 并在拆箱时抛空指针异常，正确答案是 0。
  • 错误写法：把 data 的语义理解成「恰好等于该串的键之和」。用例 insert("apple", 3)、sum("ap") → 按此语义 data["ap"] 从未被赋值，返回 0，正确答案是 3。

相似题目

题目 难度 考察点
677. 键值映射 中等 与本题同题，适合对照哈希预摊与 Trie 节点挂权值两种实现
208. 实现 Trie (前缀树) 中等 节点只需布尔标记，不涉及权值累加与覆盖更新
211. 添加与搜索单词 - 数据结构设计 中等 查询含通配符，无法预摊到固定前缀，必须在树上分支搜索
648. 单词替换 中等 同为前缀枚举，但要的是最短命中而非区间聚合
1268. 搜索推荐系统 中等 前缀上挂的是有序候选列表而非数值，聚合方式从求和变为取前三
720. 词典中最长的单词 中等 判定沿整条路径累积，考察逐字符可达性而非某点的聚合值
745. 前缀和后缀搜索 困难 同样在写入侧预摊，但键要同时编码前缀与后缀两端约束