Design and implement a TwoSum class. It should support the following operations: add
and find
.
add
- Add the number to an internal data structure.
find
- Find if there exists any pair of numbers which sum is equal to the value.
Example 1:
add(1); add(3); add(5); find(4) -> true find(7) -> false
Example 2:
add(3); add(1); add(2); find(3) -> true find(6) -> false
用HashMap, save with count
class TwoSum { public: /** Initialize your data structure here. */ TwoSum() { } /** Add the number to an internal data structure.. */ void add(int number) { M[number]++; } /** Find if there exists any pair of numbers which sum is equal to the value. */ bool find(int value) { auto iter = M.begin(); while(iter!=M.end()){ int key = iter->first; int count = iter->second; if(key == value - key){ if(count>1) return true; }else{ if(M.find(value - key) != M.end()){ return true; } } iter++; } return false; } private: unordered_map<int,int> M; // value and its count }; /** * Your TwoSum object will be instantiated and called as such: * TwoSum* obj = new TwoSum(); * obj->add(number); * bool param_2 = obj->find(value); */
Mistakes:
1: 开始根本没有考虑重复的情况。
上来就用了Set
哎,就是自己SB, 没办法, 水平不够, Tiger
是根本的人的问题, 再刷1000遍也没办法的,Tiger
艹
No comments:
Post a Comment