一、题目
提示：
1 <= key.length, prefix.length <= 50
key 和 prefix 仅由小写英文字母组成
1 <= val <= 1000
最多调用 50 次 insert 和 sum
二、 方法一：暴力扫描
方法一：
暴力扫描。对哈希表进行增删查改，就是注意找到prefix开头的键key的操作就行。
三、代码
class MapSum { private: unordered_map<string, int>mp; public: MapSum() { } void insert(string key, int val) { mp[key] = val; } int sum(string prefix) { int ans = 0; for(auto &[key, val]: mp){ //右下标为后一位 if(key.substr(0, prefix.size()) == prefix){ ans += val; } } return ans; } }; /** * Your MapSum object will be instantiated and called as such: * MapSum* obj = new MapSum(); * obj->insert(key,val); * int param_2 = obj->sum(prefix); */
四、方法二：字典树
方法二：字典树。
更新每个前缀prefix[i]值delta：
如果key不存在，则delta=val
如果key存在，则key对应的前缀值都增加val - cnt[key]
sum操作就直接在前缀树上搜索给定的前缀对应的值，如果给定的前缀不在前缀树中则返回0。
四、方法二：字典树 方法二：字典树。 更新每个前缀prefix[i]值delta： 如果key不存在，则delta=val 如果key存在，则key对应的前缀值都增加val - cnt[key] sum操作就直接在前缀树上搜索给定的前缀对应的值，如果给定的前缀不在前缀树中则返回0。 ———————————————— 版权声明：本文为CSDN博主「山顶夕景」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_35812205/article/details/122693919
