# 170 Two Sum III - Data structure design

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,
find(4) -> true
find(7) -> false
The Idea: Maintain a hash table of numbers. Since we are only managing pair-wise elements, map whether or not the number is been repeated. If so, this tells us that it can used twice. For example, if `value = 12` and we have `[6:true]`, we can return true. In general, we iterate through the hash table, and look the difference that is the current difference between i and value. If the difference is found, we know that i exists (because we iterated through it) and the difference also exist, which together make up the value.
Complexity: O(N) time for add (as the hash table grows it will occasionally have to rehash on expansion) and find. O(N) space.
class TwoSum {
public:
/** Initialize your data structure here. */
TwoSum() {}
/** Add the number to an internal data structure.. */
if (nums.find(number) == nums.end())
nums.insert({number, false});
else nums[number] = true;
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
bool find(int value) {
for (auto i : nums) {
int diff = value - i.first;
if (diff != i.first && nums.find(diff) != nums.end()) {
return true;
}
else if (diff == i.first && nums.find(diff) != nums.end() && nums[diff]) {
return true;
}
}
return false;
}
unordered_map<int, bool> nums;
};