HashSet.add(n)与myList.append(n)时间复杂度差异及LeetCode超时答疑

你的代码超时的核心问题不在append和add的时间复杂度差异，而是出在n in tempset的底层实现上，具体拆解如下：

1. 先明确：list.append()和set.add()的时间复杂度 #

你说得没错，平均情况下二者都是O(1)：

• list.append()：Python列表是动态数组，默认在尾部追加元素，只要数组还有预留空间，就是直接赋值操作，时间复杂度O(1)；只有当数组满了需要扩容时，才会触发一次O(n)的内存拷贝，但这属于均摊O(1)，整体不影响长期效率。
• set.add()：Python集合基于哈希表实现，添加元素时先计算哈希值找到对应桶位置，只要没有严重哈希冲突，就是O(1)操作；哈希表扩容时会有一次O(n)的重哈希，但同样是均摊O(1)。

2. 真正的瓶颈：n in tempset的实现差异 #

这才是导致超时的关键：

• 对于列表：n in tempset是线性遍历查找——从列表第一个元素开始逐个比对，直到找到目标元素或遍历完整个列表。假设当前列表长度为k，这一步的时间复杂度是O(k)。
  你的循环会遍历整个nums数组，每次都要做一次O(k)的查找，总时间复杂度是O(n²)。当nums长度达到10^5级别时，O(n²)的操作会直接触发超时。
• 对于集合：n in tempset是哈希表直接定位——通过元素的哈希值直接找到对应桶，平均情况下只需要常数次比对就能确定元素是否存在，时间复杂度是O(1)。
  整个循环的总时间复杂度是O(n)，对于大数组来说效率差几个数量级，自然不会超时。

3. 优化后的代码示例 #

修改为集合后的高效实现如下：

def containsDuplicate(nums: list[int]) -> bool:
    tempset = set()
    for n in nums:
        if n in tempset:
            return True
        else:
            tempset.add(n)
    return False

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