解决LeetCode存在重复元素问题中的Python TLE（超时）问题

问题背景 #

给定整数数组nums，若数组中存在至少一个重复元素则返回true，所有元素均唯一则返回false。约束条件：数组长度范围为1 <= nums.length <= 10^5，元素取值范围-10^9 <= nums[i] <= 10^9。

用户提交的双重循环代码本地运行正常，但提交时出现Time Limit Exceeded（TLE）：

class Solution(object):
    def containsDuplicate(self, nums): #self - boolean, nums - list

        count = 0
        for i in range(0,len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] == nums[j]:
                    count += 1
                    
        if count>0 :
            return True
        else:
            return False

超时原因 #

上述代码使用双重循环，时间复杂度为O(n²)。当数组长度n=10^5时，总运算量达到10^10级别，远超LeetCode的时间限制，因此触发超时。

优化方案 #

方案1：利用集合（Set）检测重复

集合的查找和插入操作平均时间复杂度为O(1)，整体时间复杂度O(n)，空间复杂度O(n)。遍历数组时，每遇到一个元素先检查是否已在集合中，存在则直接返回true，否则将元素加入集合：

class Solution(object):
    def containsDuplicate(self, nums):
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

方案2：排序后检查相邻元素

先对数组排序（时间复杂度O(n log n)），再遍历数组检查相邻元素是否相等。排序后重复元素会相邻，一旦发现相等即可返回true：

class Solution(object):
    def containsDuplicate(self, nums):
        nums.sort()
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                return True
        return False

方案说明 #

• 集合方案：适合对时间要求更高的场景，用空间换时间，10^5级别的元素能快速处理。
• 排序方案：空间复杂度更低（若使用原地排序则为O(1)），O(n log n)的时间复杂度对于10^{5元素来说，运算量约为1.7×10}6次，完全符合时间要求。

内容的提问来源于stack exchange，提问作者Sathvik Goud Sarva