# 677. Map Sum Pairs

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
``````

``````class MapSum {
public:
/** Initialize your data structure here. */
MapSum() {}

void insert(string key, int val) {
int diff = val - m[key].first, n = key.size();
m[key].first = val;
for (int i = n - 1; i > 0; --i) {
m[key.substr(0, i)].second += diff;
}
}

int sum(string prefix) {
return m[prefix].first + m[prefix].second;
}

private:
unordered_map<string, pair<int, int>> m;
};
``````

``````class MapSum {
public:
/** Initialize your data structure here. */
MapSum() {}

void insert(string key, int val) {
m[key] = val;
}

int sum(string prefix) {
int res = 0, n = prefix.size();
for (auto it = m.lower_bound(prefix); it != m.end(); ++it) {
if (it->first.substr(0, n) != prefix) break;
res += it->second;
}
return res;
}

private:
map<string, int> m;
};
``````

https://discuss.leetcode.com/topic/103924/java-map-solution

https://discuss.leetcode.com/topic/104006/c-easy-solution-ordered-map

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation