关于LeetCode经典两数之和问题公认Python解法的时间复杂度疑问

Hey MikeyS, great question—this is a super common confusion when you're first wrapping your head around hash table-based algorithms! Let's break this down clearly:

核心误解：哈希表查找 vs 线性遍历 #

你的疑问点在于认为target - nums[i] in lookup这个操作是O(n)的，但这里的lookup是Python的dict（字典），而字典是基于哈希表实现的数据结构。

哈希表的关键特性就是：平均情况下，键的存在性检查（也就是x in dict）是O(1)的常数时间操作。这和数组的线性查找完全不同——如果是在列表里做x in list，确实需要逐个遍历元素，时间是O(n)，但哈希表是通过计算键的哈希值直接定位到对应的存储位置，不需要遍历所有已有的键。

回到两数之和的解法 #

我们再看这个具体的代码：

def twoSum(self, nums: List[int], target: int) -> List[int]:
    lookup = {}
    for i in range(0, len(nums)):
        if target - nums[i] in lookup:
            return [i, lookup[target - nums[i]]]
        lookup[nums[i]] = i

• 每次循环里的in检查是O(1)，赋值操作lookup[nums[i]] = i也是O(1)
• 整个循环最多执行n次（因为题目保证有且只有一个解，实际可能更早返回）
• 所以总的时间复杂度是O(n)，而不是你担心的O(n²)

补充说明最坏情况 #

理论上，哈希表的查找在最坏情况下可能退化到O(n)（比如所有键的哈希值都冲突，变成了链表结构），但Python的字典实现已经做了很多优化（比如动态扩容、良好的哈希函数设计），这种极端情况在实际刷题场景中几乎不会遇到，而且题目给定的输入也不会刻意构造这种情况，所以我们通常说这个解法的时间复杂度是O(n)。

空间换时间的思路 #

这个解法用O(n)的空间复杂度（存储最多n个键值对）换来了O(n)的时间复杂度，对比暴力解法的O(n²)时间、O(1)空间，是典型的空间换时间的优化思路。

内容的提问来源于stack exchange，提问作者MikeyS