哈希算法题目：两数之和 III - 数据结构设计 题目描述 设计一个数据结构 TwoSum ，支持以下两种操作： add(number) ：向数据结构添加一个数 number 。 find(value) ：检查是否存在任意一对数字，其和等于 value 。若存在返回 true ，否则返回 false 。 注意： 添加的数可能包含重复值（例如多次添加同一个数）。 在 find 操作中，需要确保找到的两个数可以是同一个数（但必须是添加过两次的同一个数），例如添加 [3, 3] 后， find(6) 应返回 true 。 解题思路 核心需求分析 ： 需要高效支持动态添加数字和快速查询是否存在满足条件的数对。 重复数字的存在要求记录每个数字的出现频次，而不仅仅是存在性。 数据结构选择 ： 使用哈希表（字典）存储每个数字及其出现次数。键为数字，值为该数字被添加的次数。 例如：添加 [1, 3, 3, 5] 后，哈希表为 {1:1, 3:2, 5:1} 。 find 操作的逻辑： 遍历哈希表中的每个数字 num ，计算补数 complement = value - num 。 分两种情况： 若 complement == num ，则需要检查该数字的出现次数是否至少为 2（例如两个 3 的和为 6）。 若 complement != num ，则需要检查补数是否存在于哈希表中。 注意避免同一数字被重复使用（如仅有一个 3 时无法匹配自身）。 逐步示例 初始化： TwoSum 对象内部哈希表 freq = {} 。 操作序列： add(1) → freq = {1:1} add(3) → freq = {1:1, 3:1} add(3) → freq = {1:1, 3:2} add(5) → freq = {1:1, 3:2, 5:1} 查询示例： find(4) ：遍历哈希表： 取 num=1 ，补数 complement=3 ，存在且 3≠1 → 返回 true 。 find(6) ： 取 num=3 ，补数 complement=3 ，需检查出现次数 freq[3]≥2 → 满足 → 返回 true 。 find(7) ： 遍历所有键均不满足条件（如 num=5 时补数为 2，但 2 不存在） → 返回 false 。 复杂度分析 add 操作：时间复杂度 O(1)，直接更新哈希表。 find 操作：时间复杂度 O(n)，需要遍历哈希表的所有键（n 为不同数字的个数）。 空间复杂度：O(n)，存储所有不重复数字及其频次。 边界情况 多次添加同一数字时，频次正确累加。 查询时注意数字匹配自身的情况（频次需 ≥2）。 空数据结构时 find 直接返回 false 。