LeetCode LCR 066. 键值映射

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

题目描述

✅ LCR 066. 键值映射

image-20260929011311088

image-20260929011311089

题意分析

维护字符串到整数的映射。insert(key, val) 写入键值，键已存在时用新值覆盖旧值；sum(prefix) 返回当前所有以该前缀开头的键的值之和。

前缀可以等于整个键，此时该键也参与求和；没有键匹配时返回 $0$。题目只查询非空前缀，键和前缀都只含小写字母。

解法：按新旧差值更新前缀聚合

核心思路

[!blue]

一个键的变化只会影响它自己的非空前缀。长度为 L 的键共有 L 个这样的前缀，因此可以在插入时更新这些聚合值，查询时直接读取给定前缀的结果。

当前实现维护两张表：t[key] 记录完整键当前的值；data[prefix] 记录所有以此前缀开头的键的值之和。前者提供覆盖更新所需的旧值，后者直接回答前缀查询。

插入时先取旧值 old，不存在就按 $0$ 处理，再将 t[key] 改为 val。对于该键的每个前缀，原聚合值已经包含一份 old，现在只需把这份贡献换成 val，所以统一增加 val - old，不能再次增加整个新值。

这一步保持了聚合不变量：键自身的前缀都恰好修正了新旧差额，其他前缀不包含这个键、无需改变，其他键的贡献也保持不动。因此更新之后，每个 data[prefix] 仍等于匹配键的当前值之和。

首次插入时差值等于新值；覆盖为更小的值时差值为负，正好扣掉旧值多出的部分；再次写入相同值时差值为 $0$，聚合结果不变。前缀长度要枚举到 L 本身，因为完整键也是自己的前缀。

查询只返回 data[prefix]，缺失则为 $0$。不能再把更长前缀的聚合值累加进来，因为它们包含的键已经在当前前缀的值中计算过。

解题步骤

  1. 初始化完整键值表 t 和前缀聚合表 data。
  2. 插入时先读取 old = t[key]，缺失取 $0$，再保存新值。
  3. 枚举长度 $1$ 到键长的全部前缀，让每个聚合值增加 val - old。
  4. 查询给定前缀的聚合值，不存在时返回 $0$。

代码实现

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]
}

复杂度分析

  • 时间复杂度：长度为 L 的键插入时，枚举 L 个前缀，各前缀的哈希成本随长度增长，期望时间为 $O(L^2)$；长度为 P 的前缀查询期望为 $O(P)$。虽然查询只有一次查表，仍需考虑字符串哈希的字符成本。
  • 空间复杂度：设不同完整键的数量为 N，最大键长为 L，保存完整键和全部前缀的空间上界为 $O(NL^2)$；相同前缀在聚合表中只占一个条目。

关键点总结

[!green]

  • 完整键表保存当前单点值，前缀表保存包含多个键的聚合值，二者的含义不同。
  • 覆盖更新传播的是新值减旧值，使旧贡献被替换，而不是不断累加历史写入。
  • 更新范围恰好是当前键的所有非空前缀，必须包含整个键。

易错点总结

[!yellow]

  • 先覆盖完整键再读取旧值，会算出错误的零差量；旧值必须先保存。
  • 每次给前缀增加新值而不是差值，会把同一键的历史值重复计算。
  • 前缀枚举只写到长度小于键长，会漏掉完整键查询。
  • sum 只读当前前缀的聚合值，再累加更长前缀会重复计数。

相似题目

题目 难度 关联与区别
208. 实现 Trie (前缀树) 中等 前缀路径结构相同，本题节点还聚合所有后代单词的值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/84110316
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！