hashSet.add(n) 和 myList.append(n) 在时间复杂度方面有什么区别？ [重复]

Question

开始leetcode并出现Time Exceed Limit错误。

这是函数：

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

当我只使用数组（列表）时，它会给出错误。如果 tempset 是 set()，则它不是。 两个操作的时间复杂度有什么区别？他们不应该都以恒定的时间运行吗？或者问题出在

n in tempset

以及它如何在幕后计算它？

Answer 1

这里的问题在于线路 -

if n in tempset:

当 tempset 是一个列表时，上面这行代码需要 O(n) 来执行，因为它会迭代每个索引来执行检查。

当tempset是集合时，上面这行代码的执行时间为O(1)。集合被实现为哈希表，它们使用哈希函数来快速定位集合中的元素，使得成员资格测试非常高效。