LeetCode 677. 键值映射

2021-09-29 HGNULB 约 10 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 677. 键值映射

题意分析

要什么：设计一个映射，支持两种操作。insert(key, val)：写入一个键值对，如果这个键已经存在，就用新值覆盖旧值；sum(prefix)：返回所有以 prefix 开头的键所对应的值之和。
约束透露的信号：查询的粒度是前缀而不是精确键，这一点直接指向字典树——前缀在 Trie 上就是一条从根出发的路径，「所有以某前缀开头的键」正好是这条路径末端节点的整棵子树。而「覆盖更新」这四个字是本题真正的坑：如果节点上只会做加法，同一个键被插入两次就会被重复计入，所以必须能感知到「这个键之前是多少」。两种操作都会被频繁调用，说明二者都应做到与键长成正比、与已有键的数量无关。
边界：prefix 可能是某个键的完整形式（此时该键自身也要计入）；prefix 也可能在树中根本不存在（返回 0）；同一个键可以被反复插入任意多次，只有最后一次的值有效；值可以是任意整数，覆盖时的增量可能为负。

解法：Trie + 增量更新

核心思路

最直接的实现是一个普通哈希表：insert 就是 put，sum 遍历所有键、挑出以 prefix 开头的累加。insert 是 $O(L)$ 很好，但 sum 要扫全表并逐个做前缀比较，代价 $O(NL)$，键一多就慢。
瓶颈在于哈希表把键打散了，「共享同一前缀的键」在存储上毫无关联，只能靠一次次字符串比较重新找出来。
换成 Trie 就把这层关系显式建了出来：从根到某节点的路径恰好是一个前缀，而该节点的整棵子树里的所有终止节点，就是全部以此为前缀的键。于是 sum(prefix) 只需走到 prefix 对应的节点，再问「你子树里的值加起来是多少」。
若每次查询都现场遍历子树，代价仍与子树大小有关。更好的做法是把答案预先摊到路径上：每个节点维护一个 sum 字段，含义固定为「所有以该节点对应路径为前缀的键，其当前值之和」。这就是本解法要维护的不变量。插入一个键时，它会影响且仅影响自己这条路径上的每一个节点（根、每个前缀、直到自身），所以沿路径逐个更新即可，查询直接读取，$O(1)$ 出结果。
最后处理覆盖语义：既然节点上存的是「和」，重复插入同一个键就必须只加差量。为此额外用一张哈希表记录每个键的当前值，插入时计算 delta = 新值 - 旧值（键不存在则旧值按 0 算），把 delta 而不是 val 沿路径累加。这样无论插入多少次，节点上的和永远等于「各键最新值之和」。

解题步骤

节点结构定义为「26 个子指针 + 一个 sum 字段」，同时准备一张 key -> 当前值 的哈希表。为什么 Trie 之外还要一张哈希表：Trie 上存的是聚合值，无法反查某个具体键当前是多少；而计算差量必须知道旧值，这张表就是专门为覆盖语义服务的。

insert 先取出旧值（缺省为 0），算出 delta = val - old，再把新值写回哈希表。为什么先算差量再写回：写回之后旧值就丢了；顺序反了会让 delta 恒为 0，Trie 上的和永远不更新。

从根开始，先给根节点加上 delta，再沿 key 的每个字符下沉，缺失的子节点就新建，每下沉一层就给新节点加上 delta。为什么根节点也要加：根对应空前缀，sum("") 应当返回所有键之和，语义上必须一致；即便本题不会查询空前缀，保持不变量完整才不会在扩展时出错。为什么是「下沉后再加」而不是「加了再下沉」：要保证每个被加的节点都恰好对应 key 的一个真实前缀，写反会让最后一个字符对应的节点漏掉更新。

sum(prefix) 从根沿 prefix 的字符下沉，任何一步子指针为空就返回 0，走完则返回当前节点的 sum。为什么中途断链要返回 0 而不是继续：断链说明没有任何键以此为前缀，和自然是 0。为什么走完直接返回 sum 而不必再遍历子树：不变量保证这个字段已经是子树内全部键值之和，这正是预先摊派的收益。

以一串调用走一遍。insert("apple", 3)：哈希表里没有 apple，旧值 0、delta = 3；沿路径更新，得到 root.sum = 3，a、ap、app、appl、apple 五个节点的 sum 全为 3。此时 sum("ap") 走到 ap 节点返回 3。接着 insert("app", 2)：app 是新键，delta = 2；更新后 root.sum = 5，a 和 ap 变成 5，app 变成 5（3 + 2），而 appl、apple 不在这条更短的路径上，保持 3。此时 sum("ap") 返回 5，正是 3 + 2。再执行 insert("apple", 5) 触发覆盖：哈希表中 apple 的旧值是 3，delta = 5 - 3 = 2；沿 apple 这条路径更新，root.sum = 7，a、ap、app 各加 2 变成 7，appl 与 apple 各加 2 变成 5。此时 sum("ap") 返回 7，验证一下：当前两个键是 apple = 5 与 app = 2，和恰为 7；若当初错误地把 val 而不是 delta 累加，这里会得到 10。最后 sum("b") 在根上找不到 b 的子指针，直接返回 0。

代码实现

// 核心实现：Trie + 增量更新，维护必要状态并避免重复处理。
class MapSum {
    private static class Node {
        Node[] next = new Node[26];
        int sum;
    }

    private final Node root = new Node();
    private final Map<String, Integer> map = new HashMap<>();

    public void insert(String key, int val) {
        int old = map.getOrDefault(key, 0);
        int delta = val - old;
        map.put(key, val);

        Node cur = root;
        cur.sum += delta;
        for (int i = 0; i < key.length(); i++) {
            int idx = key.charAt(i) - 'a';
            if (cur.next[idx] == null) {
                cur.next[idx] = new Node();
            }
            cur = cur.next[idx];
            cur.sum += delta;
        }
    }

    public int sum(String prefix) {
        Node cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            int idx = prefix.charAt(i) - 'a';
            if (cur.next[idx] == null) {
                return 0;
            }
            cur = cur.next[idx];
        }
        return cur.sum;
    }
}

// 核心实现：Trie + 增量更新，维护必要状态并避免重复处理。
type trieNode677 struct {
    next [26]*trieNode677
    sum  int
}

type MapSum struct {
    root *trieNode677
    mp   map[string]int
}

func Constructor() MapSum {
    return MapSum{
        root: &trieNode677{},
        mp:   make(map[string]int),
    }
}

func (m *MapSum) Insert(key string, val int) {
    old := m.mp[key]
    delta := val - old
    m.mp[key] = val

    cur := m.root
    cur.sum += delta
    for i := 0; i < len(key); i++ {
        idx := int(key[i] - 'a')
        if cur.next[idx] == nil {
            cur.next[idx] = &trieNode677{}
        }
        cur = cur.next[idx]
        cur.sum += delta
    }
}

func (m *MapSum) Sum(prefix string) int {
    cur := m.root
    for i := 0; i < len(prefix); i++ {
        idx := int(prefix[i] - 'a')
        if cur.next[idx] == nil {
            return 0
        }
        cur = cur.next[idx]
    }
    return cur.sum
}

复杂度分析

时间复杂度：insert 与 sum 均为 $O(L)$，L 是键或前缀的长度。凭什么：插入只沿一条路径走 L 步，每步做一次数组寻址、至多一次建节点和一次加法；查询同样只沿一条路径走 L 步并读取一个字段，都与已有键的数量无关。

空间复杂度：$O(26 \sum key )$。凭什么：Trie 的节点数不超过所有键的字符总数，每个节点固定持有 26 个子指针；辅助哈希表额外占 $O(\sum key )$，量级更小。

关键点总结

把聚合值摊派到路径上是 Trie 的高阶用法：节点不再只回答「有没有」，而是携带整棵子树的统计量（和、计数、最大值都可以）。代价是每次插入要沿路径全量维护，收益是查询降到 $O(L)$ 且与数据量无关。

可覆盖的写入必须走差量。凡是「聚合结构 + 可修改的原始值」的组合（Trie 前缀和、树状数组单点修改、缓存里的统计计数），都要先取旧值算出增量再更新，并额外维护一张「当前值」的表。这是本题真正的考点，也是它比普通 Trie 高一档的原因。

节点字段的含义要一句话说死：「以我为前缀的所有键的当前值之和」。含义固定后，插入时该加什么、查询时该读什么都变得没有歧义；含义含糊就会写出「有时是子树和、有时是自身值」的混乱代码。

根节点代表空前缀，它也必须参与维护。很多实现漏掉这一句，虽然常规用例发现不了，但一旦查询空前缀或把结构复用到别处就会暴露。

面试视角：先讲清「为什么哈希表不够」，再讲「Trie 如何把前缀关系显式化」，最后主动抛出「重复插入同一个键怎么办」并给出差量方案——面试官通常就是靠这个追问区分候选人是否真的想清楚了，而不是背了一个 Trie 模板。

易错点总结

错误写法：沿路径累加 val 而不是 delta；用例 insert("apple", 3) 后再 insert("apple", 5)，然后 sum("ap") → 返回 8，正确答案是 5，同一个键的旧值没有被扣掉。

错误写法：先把新值写进哈希表再计算 delta；用例 insert("a", 3) 后再 insert("a", 5) → old 读到的已经是 5，delta 恒为 0，Trie 上的和停留在 3，sum("a") 返回 3 而不是 5。

错误写法：只在键的末端节点累加，中间节点不更新；用例 insert("apple", 3) 后 sum("ap") → ap 节点的 sum 仍为 0，返回 0，正确答案是 3。

错误写法：sum 时走到末端后还去遍历子树重新累加；用例前缀下挂着大量键 → 结果虽对，但单次查询退化成 $O(子树大小)$，失去了摊派的意义，频繁查询时超时。

错误写法：sum 中途遇到空子指针时返回当前节点的 sum；用例 insert("apple", 3) 后 sum("apx") → 走到 ap 发现没有 x，却返回 ap 的 3，正确答案是 0。

错误写法：忘记给根节点加 delta；用例 insert("a", 3) 后 sum("") → 返回 0，正确答案是 3；同时也让「根节点的和等于全部键之和」这条不变量失效。

错误写法：下沉与累加的顺序写反，先给当前节点加再下沉，且循环写成 for i in 0..L-1；用例 insert("ab", 3) 后 sum("ab") → ab 对应的末端节点从未被累加，返回 0，正确答案是 3。

错误写法：省掉辅助哈希表，改用「在末端节点存一个 val 字段」来求旧值，但求旧值时忘了先判断路径是否已存在；用例首次 insert("apple", 3) → 沿路径查找旧值时遇到空指针崩溃。

错误写法：字符转下标写成 key.charAt(i) - '0' 或忘记减基准字符；用例任意小写字母键 → 下标变成 49 以上，数组越界异常。

错误写法：把值当作只增不减，用无符号或非负假设去做剪枝（如「sum 为 0 就认为该分支无键」）；用例 insert("a", 5) 后 insert("a", 0) → delta 为 -5 使路径上的和归零，若据此剪枝会让后续对 a 前缀的查询提前返回，掩盖真实结构。

相似题目

题目	难度	考察点
208. 实现 Trie (前缀树)	中等	节点只需布尔标记，回答「有没有」而不做任何聚合，没有覆盖更新的问题
648. 单词替换	中等	节点存的是词根字符串，查询要在下行途中「最早命中即返回」
211. 添加与搜索单词 - 数据结构设计	中等	查询含通配符，路径不再唯一，必须在树上做分支回溯而非单链下沉