哈希算法题目：两数之和 III - 数据结构设计

题目描述：

设计一个数据结构 TwoSum，它应该支持以下两种操作：

1. add(number)：向数据结构中添加一个整数 number。
2. find(value)：检查当前数据结构中是否存在任意一对整数，它们的和等于给定的 value。如果存在，返回 true；否则，返回 false。

示例：

twoSum = TwoSum()
twoSum.add(1)     # 数据结构：[1]
twoSum.add(3)     # 数据结构：[1, 3]
twoSum.add(5)     # 数据结构：[1, 3, 5]
print(twoSum.find(4))  # 返回 True，因为 1 + 3 = 4
print(twoSum.find(7))  # 返回 False，因为没有两个数相加等于 7
twoSum.add(5)     # 数据结构：[1, 3, 5, 5]
print(twoSum.find(10)) # 返回 True，因为 5 + 5 = 10

解题过程循序渐进讲解：

这个问题是经典“两数之和”问题的变种，区别在于数据是动态添加的，并且需要支持多次查询。核心在于高效实现 find 操作。我们将探讨两种主要方法，并重点讲解基于哈希表的优化方案。

步骤 1：暴力法（理解问题，明确低效点）

最直观的想法是，内部维护一个列表 nums 来存储所有添加的数字。

• add(number)： 直接将 number 追加到 nums 末尾。时间复杂度 O(1)。
• find(value)： 使用双重循环遍历 nums 中的所有无序对 (nums[i], nums[j]) (i != j)，检查它们的和是否等于 value。时间复杂度 O(n²)，其中 n 是已添加数字的数量。在多次查询的场景下，这非常低效。

步骤 2：基于排序和双指针的思路（引出优化方向）

一个优化 find 的思路是，每次调用 find 时，先对当前 nums 列表进行排序，然后使用双指针法在 O(n) 时间内判断是否存在和为 value 的数对。

• add(number)： 依然 O(1) 追加，但破坏了列表的有序性。
• find(value)： 先排序 O(n log n)，再双指针 O(n)，总时间复杂度 O(n log n)。这比 O(n²) 好，但如果频繁 add 和 find，每次 find 都要排序，开销依然不小。

步骤 3：基于哈希表的优化方案（核心讲解）

我们追求的目标是让 find 操作尽可能快，即使以稍微增加 add 的复杂度为代价。哈希表（字典）的 O(1) 查找特性非常适合这里。

方案 3.1：单次遍历哈希表（类比经典“两数之和”）
我们可以尝试模仿经典“两数之和”的解法。在 find(value) 时，我们遍历当前所有数字，并用一个哈希集合（HashSet）来记录遍历过程中遇到的数字。对于当前遍历的数字 num，我们计算其补数 complement = value - num，然后检查这个 complement 是否已经存在于哈希集合中。如果存在，说明我们找到了和为 value 的一对数（complement 和 num），返回 True；否则，将 num 加入哈希集合，继续遍历。

但这里有一个关键问题：经典解法是给定一个静态数组，在单次遍历中完成。而在我们的问题中，数据结构内部存储的数字列表是动态增长的。如果我们在 find 内部再创建一个哈希集合并遍历所有数字，每次 find 的时间复杂度是 O(n)，空间复杂度是 O(n)（用于临时哈希集合）。虽然比 O(n²) 好，但我们能否利用一个持久的、在 add 时就维护好的数据结构，让 find 更快呢？

方案 3.2：计数哈希表（最优方案讲解）

核心思想：在 add 操作时，就维护一个计数哈希表 num_count，它的键（key）是添加的数字，值（value）是该数字出现的次数。

• add(number) 的实现：

  1. 直接更新哈希表：num_count[number] = num_count.get(number, 0) + 1。
  2. 时间复杂度：O(1)。

• find(value) 的实现：

  1. 遍历哈希表 num_count 中的所有键（即不同的数字）num。
  2. 计算补数 complement = value - num。
  3. 判断补数是否存在：
     • 情况 1：complement == num。这意味着我们需要两个相同的 num 来组成 value。此时，需要检查 num_count[num] 是否大于等于 2。如果是，返回 True。
     • 情况 2：complement != num。这意味着我们需要两个不同的数字。此时，只需检查 complement 这个键是否存在于 num_count 中。如果存在，返回 True。
  4. 如果遍历完所有键都没有找到符合条件的数对，则返回 False。

  时间复杂度：O(m)，其中 m 是哈希表中不同数字的数量。在最坏情况下（所有数字都不同），m 等于数字总数 n，所以是 O(n)。在最好情况下（数字大量重复），m 远小于 n。空间复杂度：O(n)，用于存储哈希表。

步骤 4：边界情况与示例推演

让我们用开头的例子来推演一遍计数哈希表方案：

1. 初始化：num_count = {}。
2. add(1)： num_count 变为 {1: 1}。
3. add(3)： num_count 变为 {1: 1, 3: 1}。
4. add(5)： num_count 变为 {1: 1, 3: 1, 5: 1}。
5. find(4)：
   • 遍历 num_count 键：1, 3, 5。
   • 对于 num=1：complement = 4-1 = 3。3 != 1 且 3 在 num_count 中。找到，返回 True。
6. find(7)：
   • 遍历 num_count 键：1, 3, 5。
   • num=1：complement=6，不在。
   • num=3：complement=4，不在。
   • num=5：complement=2，不在。遍历结束，返回 False。
7. add(5)： num_count 更新为 {1: 1, 3: 1, 5: 2}。
8. find(10)：
   • 遍历键：1, 3, 5。
   • num=1：complement=9，不在。
   • num=3：complement=7，不在。
   • num=5：complement=5。5 == 5，检查 num_count[5] 是否 >=2。是的（值为2）。找到，返回 True。

步骤 5：总结与代码框架（Python示例）

class TwoSum:
    def __init__(self):
        """
        初始化数据结构。
        """
        self.num_count = {}  # 计数哈希表

    def add(self, number: int) -> None:
        """
        添加一个数字到数据结构中。
        """
        self.num_count[number] = self.num_count.get(number, 0) + 1

    def find(self, value: int) -> bool:
        """
        查找是否存在任意一对数字，它们的和等于 value。
        """
        for num in self.num_count:
            complement = value - num
            if complement in self.num_count:
                # 关键：区分补数是否等于当前数本身
                if complement != num:
                    return True
                elif self.num_count[num] >= 2:  # 需要两个相同的数
                    return True
        return False

进一步思考：

• 如果数据流中 add 操作远多于 find 操作，这个方案非常高效，因为 add 是 O(1)。
• 如果 find 操作极其频繁，而数字范围有限，可以考虑在 add 时预计算所有可能的和，但这会极大增加 add 的复杂度和空间开销，通常不实用。计数哈希表方案是时间与空间的一个很好权衡。