题目描述

请实现一个 TwoSum 类，它需要支持两种操作：add 和 find。

add - 在数据集合中添加一个数。
find - 在数据集合中，是否存在两个数，它们的和等于给定的数。

样例1

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

样例2

add(3); add(1); add(2);
find(3) -> true
find(6) -> false

算法

(哈希表) $add: O(1), find: O(n)$

用哈希表统计每个数的个数。
哈希表可以用C++中的 unordered_multiset<int> nums，multiset可以存储相同元素，nums.count(x) 就是 $x$ 在集合中的个数。

add(x) - 直接将 $x$ 插入哈希表；

find(target) - 枚举集合中的每个数 $x$，判断与 $x$ 互补的数 $target - x$ 是否也在集合中。这里要注意每个数只能使用一次，所以如果恰好 $2x = target$ 时，集合中需要至少存在2个 $x$ 才可以凑出 $target$。

时间复杂度分析：add操作仅有一次哈希表的插入操作，时间复杂度是 $O(1)$，find 需要枚举集合中的每个数，时间复杂度是 $O(n)$。

C++ 代码

class TwoSum {
public:
    /** Initialize your data structure here. */
    unordered_multiset<int> nums;
    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) {
        for (int i : nums)
        {
            int count = (i + i) == value ? 1 : 0; // 每个数只能用一次
            if (nums.count(value - i) > count) return true;
        }
        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);
 */