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;
};