Two Sum III
170. Two Sum III — Data structure design
1 min readOct 9, 2020
method 1: sort and find (C++)
class TwoSum {
public:
multiset<int> nums;
set<int> good;
/** Initialize your data structure here. */
TwoSum() {
}
/** Add the number to an internal data structure.. */
void add(int number) {
nums.insert(number);
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
bool find(int value) {
if (nums.size() <= 1) return false;
if (good.count(value)) return true;
auto begin = nums.begin();
auto end = --nums.end();
while (begin!= end) {
auto thisSum = *begin + *end;
if (thisSum == value) {
good.insert(value);
return true;
}
else if (thisSum < value) {
begin++;
}
else {
end--;
}
}
return false;
}
};/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum* obj = new TwoSum();
* obj->add(number);
* bool param_2 = obj->find(value);
*/
method 2: traditional two sum (Python)
class TwoSum:def __init__(self):
"""
Initialize your data structure here.
"""
self.cnt = collections.defaultdict(int)def add(self, number: int) -> None:
"""
Add the number to an internal data structure..
"""
self.cnt[number] += 1def find(self, value: int) -> bool:
"""
Find if there exists any pair of numbers which sum is equal to the value.
"""
return any(value-num in self.cnt and (value-num !=num or self.cnt[num] > 1) for num in self.cnt)# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)
# param_2 = obj.find(value)
