正文
LeetCode 677. Map Sum Pairs 键值映射(C++/Java)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目：
Implement a MapSum class with insert, and sum methods.
For the method insert, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.
For the method sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.
Example 1:
Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
分析：
实现一个MapSum类，拥有insert和sum两个方法。
对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。
对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。
使用一个map用来存储键值对，每当insert一个字符串时，将这个字符串的所有前缀和val保存到另一个map中，同时插入字符串时，如果map中已经有这个这个前缀的话，就需要更新值。
例如原来插入一个apple-3，此时保存前缀的map中保存a-3，ap-3，app-3，appl-3，apple-3。如果再新插入一个ape-2，我们就要将a-3更新成为a-5，ap-3更新为ap-5，同时新加一个ape-2，也就是将原来的值和新的前缀值相加。
程序：
C++
class MapSum {
public:
/** Initialize your data structure here. */
MapSum() { } void insert(string key, int val) {
int diff = val - vals[key];
for(int i = ; i <= key.size(); ++i){
sums[key.substr(, i)] += diff;
}
vals[key] = val;
} int sum(string prefix) {
return sums[prefix];
}
private:
map<string, int> vals;
map<string, int> sums;
};
Java
class MapSum { /** Initialize your data structure here. */
public MapSum() { } public void insert(String key, int val) {
int diff = val - vals.getOrDefault(key, 0);
for(int i = 1; i <= key.length(); ++i){
String s = key.substring(0, i);
sums.put(s, sums.getOrDefault(s, 0) + diff);
}
vals.put(key, val);
} public int sum(String prefix) {
return sums.getOrDefault(prefix, 0);
}
private HashMap<String, Integer> vals = new HashMap<>();
private HashMap<String, Integer> sums = new HashMap<>();
}
