170 Two Sum III - Data structure design
Design and implement a TwoSum class. It should support the following operations:
addandfind.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
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.. */
void add(int number) {
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;
};
Last modified 4yr ago