LeetCode Q170: Two Sum III - Data structure desing

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.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Solution:
O(1) add
O(n) find: using hash table.

Need to care about when two numbers are equal. In this case, this number has to be added at least twice.

By using unordered_map::count() is much faster than unordered_map::find().

	class TwoSum {
	public:
	// Add the number to an internal data structure.
	void add(int number) {
	myMap[number]=myMap[number]+1;
	}
	// Find if there exists any pair of numbers which sum is equal to the value.
	bool find(int value) {
	for(auto it: myMap){
	int p0=it.first;
	int p1=value-p0;
	if(p1==p0){
	if(myMap[p1]>1)
	return true;
	continue;
	}
	if(myMap.count(p1))
	return true;
	}
	return false;
	}
	unordered_map<int, int> myMap;
	};
	// Your TwoSum object will be instantiated and called as such:
	// TwoSum twoSum;
	// twoSum.add(number);
	// twoSum.find(value);

view raw Q170TwoSumIII.cpp hosted with ❤ by GitHub