【C++刷题】力扣-#170-两数之和III-数据结构设计

题目描述

设计一个数据结构来找出一个整数数组中是否有两个数的和为特定目标值 target。该数据结构包含如下两个操作：

1. add：向数据结构中添加一个数。
2. find：返回数据结构中是否存在两个数的和等于给定的目标值 target，如果存在则返回 true，否则返回 false。

示例

add 示例：

add("num1")
add("num2")

find 示例：

find("9")

题解

这个问题可以通过使用哈希表来解决。哈希表可以用来存储已经添加的数以及它们出现的次数。

1. 初始化：创建一个哈希表 hashMap 来存储添加的数。
2. add 操作：当添加一个数时，将其添加到 hashMap 中，并更新它的计数。
3. find 操作：当查找两个数的和时，遍历 hashMap 中的所有数，对于每个数 num，检查 target - num 是否也在 hashMap 中。如果存在，并且 num 不等于 target - num 或者 num 出现了至少两次（以处理相同数相加的情况），则返回 true。如果遍历结束后没有找到，则返回 false。

代码实现

class TwoSum {
private:unordered_map<int, int> hashMap;public:void add(int number) {hashMap[number]++;}bool find(int target) {for (const auto& pair : hashMap) {int num = pair.first;int count = pair.second;int complement = target - num;if (complement == num && count < 2) continue; // 相同数相加且只出现一次if (complement == num && count >= 2) return true; // 相同数相加且出现至少两次if (hashMap.find(complement) != hashMap.end()) return true; // 不同数相加}return false;}
};

复杂度分析

● add 操作的时间复杂度：O(1)，添加一个数到哈希表中是常数时间操作。
● find 操作的时间复杂度：O(n)，其中 n 是哈希表中元素的数量。在最坏情况下，我们需要遍历哈希表中的所有数。
● 空间复杂度：O(n)，我们需要存储所有添加的数。
这个算法的优势在于它利用了哈希表的快速查找特性，使得 add 操作非常高效。find 操作虽然在最坏情况下需要遍历哈希表，但平均情况下性能仍然是可接受的。