LeetCode LCR 066. 键值映射

Categories:

题目描述
思路分析
1. 解法一：Trie 前缀和（推荐）
相似题目

题目描述

✅ LCR 066. 键值映射

思路分析

解法一：Trie 前缀和（推荐）

核心思路：

维护 key -> value 映射，更新时计算差值 delta。

Trie 节点保存经过该节点的前缀和，插入时沿路径累加 delta。

查询前缀时走到对应节点，直接返回其 sum。

复杂度分析：

时间复杂度：O(L)，其中 L 表示字符串长度。

空间复杂度：O(total)，Trie 存储所有键的字符。

import java.util.*;

class MapSum {
    private static class TrieNode {
        TrieNode[] next = new TrieNode[26];
        int sum;
    }

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

    public MapSum() {}

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

        TrieNode 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 TrieNode();
            }
            cur = cur.next[idx];
            cur.sum += delta;
        }
    }

    public int sum(String prefix) {
        TrieNode 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;
    }
}

type TrieNode struct {
    next [26]*TrieNode
    sum  int
}

type MapSum struct {
    root *TrieNode
    data map[string]int
}

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

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

    cur := m.root
    cur.sum += delta
    for i := 0; i < len(key); i++ {
        idx := key[i] - 'a'
        if cur.next[idx] == nil {
            cur.next[idx] = &TrieNode{}
        }
        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 := prefix[i] - 'a'
        if cur.next[idx] == nil {
            return 0
        }
        cur = cur.next[idx]
    }
    return cur.sum
}

相似题目

题目	难度	考察点
208. 实现 Trie (前缀树)	中等	Trie
642. 设计搜索自动补全系统	困难	Trie
648. 单词替换	中等	前缀树
820. 单词的压缩编码	中等	后缀处理
1268. 搜索推荐系统	中等	字典树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/84110316