两段containsDuplicate代码差异及时间复杂度导致TLE的原因解析

代码片段1（使用列表，出现TLE） #

def containsDuplicate(self, nums):
    """
    :type nums: List[int]
    :rtype: bool
    """
    num2=[]
    for x in nums:
        if (x in num2):
            return True
        num2.append(x)
    return False

你误以为这段代码时间复杂度是O(n)，但实际上它的时间复杂度是O(n²)。问题出在x in num2这个操作上：列表的成员检查是线性遍历，每次查找都要从头扫到当前列表的末尾。最坏情况下（比如数组完全没有重复元素），第1次查找要检查1个元素，第2次检查2个，……第n次检查n个元素，总操作次数是1+2+...+n = n(n+1)/2，属于平方级复杂度。当LeetCode用超大测试用例（比如百万级元素）时，这种复杂度会导致运行超时。

代码片段2（使用集合，正常通过） #

def containsDuplicate(self, nums):
    """
    :type nums: List[int]
    :rtype: bool
    """
    num2=set()
    for x in nums:
        if (x in num2):
            return True
        num2.add(x)
    return False

这段代码改用集合后，x in num2的平均时间复杂度是O(1)。集合基于哈希表实现，成员检查是通过哈希值直接定位，不需要遍历整个集合。整个算法只需要遍历一次原数组，总时间复杂度是O(n)，完全能处理LeetCode的大测试用例，所以可以正常通过。

内容的提问来源于stack exchange，提问作者Sherlock-Holmes-2-2-1