两数之和 III - 数据结构设计

题目描述

你需要设计一个数据结构 TwoSum，支持以下两种操作：

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

示例：

twoSum = TwoSum()
twoSum.add(1)
twoSum.add(3)
twoSum.add(5)
twoSum.find(4) -> True   # 1 + 3 = 4
twoSum.find(7) -> False  # 没有两个数的和等于 7

要求：

• add 操作可能需要高效（但具体时间复杂度取决于设计选择）。
• find 操作需要尽可能高效。
• 注意：同一个数字可能被多次添加，例如 add(3) 两次，那么 find(6) 需要能够使用两个 3 来组成和。

解题思路与设计

这道题的核心是如何在动态添加数字的过程中，快速判断是否存在两个数的和等于目标值。最直接的暴力方法是：每次 find 时遍历所有已添加的数字，检查是否存在 value - num。但这样 find 的时间复杂度是 O(n)，其中 n 是已添加数字的数量。我们可以通过哈希表来优化。

步骤1：理解问题与数据特点

• 数字可能重复添加：例如两次添加 3，那么数字 3 的“可用次数”为 2。
• 对于 find(value)，我们需要检查是否存在两个（可能相同的）数字 a 和 b，使得 a + b = value。
• 如果 a 和 b 相同（例如 value = 6，且数字 3 出现了至少两次），那么需要确保该数字的计数至少为 2。

步骤2：选择数据结构

由于数字可能重复，我们需要记录每个数字的出现次数。哈希表（字典）是理想的选择：

• 键（key）：数字本身。
• 值（value）：该数字被添加的次数（计数）。

例如，添加序列 [1, 3, 3, 5] 后，哈希表为 {1:1, 3:2, 5:1}。

步骤3：设计 add 操作

• 每调用一次 add(number)，我们就在哈希表中将 number 的计数加 1。
• 如果 number 不在哈希表中，则先初始化计数为 0 再加 1。
• 时间复杂度：O(1)（假设哈希表操作平均为常数时间）。

步骤4：设计 find 操作

遍历哈希表中的每个数字 num 及其计数 count：

1. 计算补数：complement = value - num。
2. 分两种情况：
   • 如果 num != complement：那么只需要检查 complement 是否在哈希表中且计数至少为 1。
   • 如果 num == complement：那么需要该数字的计数至少为 2（因为需要两个相同的数字）。
3. 只要找到满足条件的数字对，立即返回 True；如果遍历完所有数字都没有找到，则返回 False。

时间复杂度：O(n)，其中 n 是哈希表中不同数字的数量（因为需要遍历每个不同的数字）。

步骤5：优化 find 操作

• 上述方法在 find 时总是需要遍历整个哈希表。在某些场景下，如果 add 操作远多于 find，这可能可以接受。但如果 find 操作也很频繁，我们可以考虑进一步优化。
• 另一种思路：在每次 add 时预计算所有可能的两数之和（与已添加数字的组合），并将和存入一个“和哈希表”中。这样 find 操作可以 O(1) 完成，但 add 操作会变为 O(n)，且空间复杂度为 O(n²)（因为需要存储所有两数之和）。这对于大数据量不可行。
• 因此，我们采用折中的方案：使用计数哈希表，add 为 O(1)，find 为 O(n)。

步骤6：边界情况与注意事项

1. 空数据结构：未添加任何数字时，find 任何值都应返回 False。
2. 数字 0：例如添加了 0，find(0) 需要两个 0，因此需要检查计数是否 ≥2。
3. 大整数：注意整数的范围，但哈希表可以处理大整数。
4. 负数：哈希表同样可以处理负数，算法逻辑不变。

步骤7：代码实现（Python示例）

class TwoSum:
    def __init__(self):
        # 哈希表，key: 数字, value: 出现次数
        self.num_counts = {}

    def add(self, number: int) -> None:
        # 添加数字，更新计数
        self.num_counts[number] = self.num_counts.get(number, 0) + 1

    def find(self, value: int) -> bool:
        # 遍历哈希表中的每个数字
        for num in self.num_counts:
            complement = value - num
            # 情况1：两个数不同
            if num != complement:
                if complement in self.num_counts:
                    return True
            # 情况2：两个数相同
            else:
                # 需要该数字至少出现两次
                if self.num_counts[num] >= 2:
                    return True
        return False

步骤8：算法复杂度分析

• 时间复杂度：
  • add(number)：O(1)（平均情况）。
  • find(value)：O(k)，其中 k 是哈希表中不同数字的数量（即 len(num_counts)）。
• 空间复杂度：O(k)，用于存储每个不同数字的计数。

步骤9：测试与验证

以题目示例测试：

twoSum = TwoSum()
twoSum.add(1)
twoSum.add(3)
twoSum.add(5)
print(twoSum.find(4))  # True, 1+3=4
print(twoSum.find(7))  # False

添加重复数字测试：

twoSum = TwoSum()
twoSum.add(3)
twoSum.add(3)
print(twoSum.find(6))  # True, 3+3=6

边界测试：

twoSum = TwoSum()
print(twoSum.find(0))  # False
twoSum.add(0)
print(twoSum.find(0))  # False，只有一个0，不够两个
twoSum.add(0)
print(twoSum.find(0))  # True

步骤10：进一步思考与扩展

• 如果要求 find 操作更高效，可以牺牲 add 的速度。例如，维护一个所有可能和的哈希集合，但这样 add 变为 O(n)，空间 O(n²)。
• 如果数据流中数字范围有限，可以使用数组代替哈希表来计数，这样 find 可以更快。
• 本题体现了哈希表在“快速查找补数”中的核心作用，是“两数之和”类问题的动态版本。

通过上述步骤，我们设计了一个基于哈希表计数的数据结构，平衡了 add 和 find 操作的效率，并处理了数字重复的情况。