C++实现LeetCode(170.两数之和之三 – 数据结构设计)

C++实现LeetCode(170.两数之和之三 - 数据结构设计)

题目描述

设计并实现一个 TwoSum 类。他需要支持以下操作：

• add 操作 - 将指定数字添加到内部的数据结构中。
• find 操作 - 是否存在任意一对数字之和等于指定的目标值。

示例:

TwoSum twoSum;
twoSum.add(1); // {1}
twoSum.add(3); // {1,3}
twoSum.add(5); // {1,3,5}
twoSum.find(4); // true
twoSum.find(7); // true
twoSum.find(8); // false

解题思路

题目要求设计一个支持add和find操作的TwoSum类。为了优化find操作的时间复杂度，需要将add操作的时间复杂度降到O(1)。因此，可以使用哈希表来存储添加进来的数字，并在find时利用哈希表来查找是否存在两个数之和等于目标值的情况。

在此题解中，我们利用了unordered_multiset来实现哈希表。多重集合是允许有重复元素的集合，因此可以存储重复数字。具体实现步骤如下：

1. 首先定义一个unordered_multiset作为哈希表，用于存储所有添加进来的数字。
2. 对于add操作，直接将数字插入到unordered_multiset中即可，时间复杂度为O(1)。
3. 对于find操作，遍历unordered_multiset中的每个数字x，查找unordered_multiset中是否存在另一个数字(target - x)。注意，在unordered_multiset中查找数字的时间复杂度为O(n)，即需要遍历整个哈希表。
4. 如果查找到了两个数字之和等于目标值，则返回true，否则返回false。

完整代码实现如下：

class TwoSum {
public:
    unordered_multiset<int> nums;

    /** Initialize your data structure here. */
    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 num : nums) {
            int complement = value - num;
            if (complement != num && nums.count(complement)) {
                return true;
            }
        }
        return false;
    }
};

示例说明

示例1

TwoSum twoSum;
twoSum.add(1); // {1}
twoSum.add(3); // {1,3}
twoSum.add(5); // {1,3,5}
twoSum.find(4); // true
twoSum.find(7); // true
twoSum.find(8); // false

在上述示例中，先将数字1、3、5添加到TwoSum类的哈希表中，然后进行了三次find操作。第一次查找4，由于存在数字1和3使得它们的和等于4，因此返回true。第二次查找7，由于存在数字3和5使得它们的和等于7，因此返回true。第三次查找8，由于哈希表中不存在两个数字其和等于8，因此返回false。

示例2

TwoSum twoSum;
twoSum.add(-1); // {-1}
twoSum.add(3); // {-1, 3}
twoSum.add(10); // {-1, 3, 10}
twoSum.add(5); // {-1, 3, 10, 5}
twoSum.find(6); // true
twoSum.find(-1); // false

在上述示例中，先将数字-1、3、10、5添加到TwoSum类的哈希表中，然后进行了两次find操作。第一次查找6，由于哈希表中存在数字1和5，使得它们的和等于6，因此返回true。第二次查找-1，由于哈希表中存在数字-1，但不存在数字-2，使得二者的和等于-1，因此返回false。