友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
677. 键值映射
设计一个 map ，满足以下几点:
-
字符串表示键，整数表示值
-
返回具有前缀等于给定字符串的键的值的总和
实现一个 MapSum 类：
-
MapSum()初始化MapSum对象 -
void insert(String key, int val)插入key-val键值对，字符串表示键key，整数表示值val。如果键key已经存在，那么原来的键值对key-value将被替代成新的键值对。 -
int sum(string prefix)返回所有以该前缀prefix开头的键key的值的总和。
示例 1：
输入：
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
输出：
[null, null, 3, null, 5]
解释：
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // 返回 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // 返回 5 (apple + app = 3 + 2 = 5)
提示：
-
1 <= key.length, prefix.length <= 50 -
key和prefix仅由小写英文字母组成 -
1 <= val <= 1000 -
最多调用
50次insert和sum
思路分析
最简单的就是使用哈希存储添加的值，求和时，再遍历所有键值对。
效率更高的做法是使用前缀树。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-05-07 23:24:40
*/
class MapSum {
// 好简单的 Trie
class Trie {
Trie[] children = new Trie[26];
int value;
}
private Trie root;
private Map<String, Integer> map;
public MapSum() {
map = new HashMap<>();
root = new Trie();
}
public void insert(String key, int val) {
int delta = val - map.getOrDefault(key, 0);
map.put(key, val);
Trie node = root;
for (char c : key.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new Trie();
}
node = node.children[c - 'a'];
// 在树的一条从顶到叶的所有节点都存储了变化
node.value += delta;
}
}
public int sum(String prefix) {
Trie node = root;
for (char c : prefix.toCharArray()) {
if (node.children[c - 'a'] == null) {
return 0;
}
node = node.children[c - 'a'];
}
// 这里是已经汇总好的值了。
return node.value;
}
}