江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第170题：两数之和 III - 数据结构设计

设计一个接受整数流的数据结构，并能够检查它们中是否有一对整数的和等于特定值。 实现 TwoSum 类： - TwoSum() 初始化 TwoSum 对象，使其为空 - void add(int number) 向数据结构添加一个数 number - boolean find(int value) 寻找数据结构中是否存在一对整数，它们的和等于 value。如果

题目描述

设计一个接受整数流的数据结构，并能够检查它们中是否有一对整数的和等于特定值。

实现 TwoSum 类：

  • TwoSum() 初始化 TwoSum 对象，使其为空
  • void add(int number) 向数据结构添加一个数 number
  • boolean find(int value) 寻找数据结构中是否存在一对整数，它们的和等于 value。如果存在，返回 true；否则，返回 false

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例：

输入：
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
输出：
[null, null, null, null, true, false]

解释：
TwoSum twoSum = new TwoSum();
twoSum.add(1);   // [] --> [1]
twoSum.add(3);   // [1] --> [1,3]
twoSum.add(5);   // [1,3] --> [1,3,5]
twoSum.find(4);  // 1 + 3 = 4，返回 true
twoSum.find(7);  // 没有两个整数加起来等于 7，返回 false

提示

  • -10^5 <= number <= 10^5
  • -2^31 <= value <= 2^31 - 1
  • 最多调用 10^4 次 add 和 find

解题思路

方法一：哈希表

使用哈希表存储所有添加的数字及其出现次数，当查找时，检查与每个已有数字互补的数字是否也在哈希表中。 关键点：

  1. 用哈希表存储每个数字及其出现次数
  2. 查找时，对于每个已有的数字，检查目标值减去该数字后的结果是否也在哈希表中
  3. 注意处理元素重复的情况

时间复杂度：

  • add: O(1)
  • find: O(n)，其中n是不同数字的数量

空间复杂度：O(n)，需要存储所有不同的数字

方法二：双指针（基于排序）

虽然此方法在本题不是最优解，但对于某些特定场景仍有参考价值。 关键点：

  1. 维护一个排序的数组
  2. 查找时使用双指针从两端向中间扫描
  3. 添加新元素时可能需要重新排序

时间复杂度：

  • add: O(n log n)
  • find: O(n)

空间复杂度：O(n)

代码实现

C# 实现

方法一：哈希表

public class TwoSum {
    private Dictionary<int, int> numCounts;

    public TwoSum() {
        numCounts = new Dictionary<int, int>();
    }
    
    public void Add(int number) {
        if (!numCounts.ContainsKey(number)) {
            numCounts[number] = 0;
        }
        numCounts[number]++;
    }
    
    public bool Find(int value) {
        foreach (var num in numCounts.Keys) {
            int complement = value - num;
            if (complement == num) {
                // 如果互补的数字就是当前数字自己，需要确保至少有两个
                if (numCounts[num] > 1) {
                    return true;
                }
            } else if (numCounts.ContainsKey(complement)) {
                return true;
            }
        }
        return false;
    }
}

Python 实现

方法一：哈希表

class TwoSum:
    def __init__(self):
        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
            if complement == num:
                # 如果互补的数字就是当前数字自己，需要确保至少有两个
                if self.num_counts[num] > 1:
                    return True
            elif complement in self.num_counts:
                return True
        return False

C++ 实现

方法一：哈希表

class TwoSum {
private:
    unordered_map<int, int> numCounts;

public:
    TwoSum() {
        
    }
    
    void add(int number) {
        numCounts[number]++;
    }
    
    bool find(int value) {
        for (const auto& pair : numCounts) {
            int num = pair.first;
            int complement = value - num;
            if (complement == num) {
                // 如果互补的数字就是当前数字自己，需要确保至少有两个
                if (numCounts[num] > 1) {
                    return true;
                }
            } else if (numCounts.count(complement) > 0) {
                return true;
            }
        }
        return false;
    }
};

性能分析

各语言实现的性能对比：

实现语言 执行用时 内存消耗 特点
C# 112 ms 46.8 MB 实现简洁，性能适中
Python 248 ms 19.6 MB 代码最简洁
C++ 84 ms 23.6 MB 性能最优

补充说明

代码亮点

  1. 使用哈希表存储数字及其频次，优化查找效率
  2. 特别处理了两个相同数字相加的情况，确保至少有两个相同的数
  3. 代码结构清晰，易于理解

常见错误

  1. 没有处理数字重复的情况，如 add(3) 添加两次，然后 find(6) 应该返回 true
  2. 使用不必要的排序操作，导致添加操作效率低下
  3. 没有正确使用哈希表，使得查找效率不高

相关题目