在重复整数检测问题中，为何HashSet比Array更快？相关疑问解析

一、两种解法的核心差异 #

1. 时间复杂度 #

• 数组解法：代码里每次执行if i in newArray时，Python需要遍历整个newArray查找元素，这一步是O(n)操作。加上外层遍历，整体时间复杂度为O(n²)——当数组长度n较大时（比如10^4级以上），运行时间会急剧上升，很容易超时。
• HashSet解法：Python的set基于哈希表实现，if n in hashset的查找操作平均时间复杂度是O(1)，哈希函数能直接定位元素存储位置。外层遍历是O(n)，所以整体时间复杂度为O(n)，大数据量下效率远高于数组解法。

2. 空间复杂度 #

两种解法的空间复杂度都是O(n)——最坏情况（数组无重复）下，都需要存储所有元素。

3. 底层逻辑差异 #

• 数组（list）是线性存储结构，查找元素只能从头遍历到尾，没有快捷路径。
• HashSet（set）通过哈希映射将元素映射到固定索引位置，查找时直接计算哈希值定位，无需遍历整个集合。

二、给数组解法添加nums.sort()的影响 #

如果在数组解法开头加上nums.sort()，整个解法的逻辑和时间复杂度都会发生变化：

1. 时间复杂度变化：排序操作的时间复杂度是O(n log n)，排序后只需遍历一次数组，检查相邻元素是否重复（nums[i] == nums[i+1]），这一步是O(n)。整体时间复杂度变为O(n log n)，比原数组解法的O(n²)快很多，但仍略逊于HashSet的O(n)。
2. 其他影响：
   • 排序会修改原数组，如果题目明确要求不能修改输入数组，需要额外复制一份数组再排序，空间复杂度仍为O(n)。
   • 排序后的解法逻辑已不同于原数组解法，不再是逐个存储检查，而是利用排序后重复元素相邻的特性完成检测。

三、面试中的适用性 #

• 原数组解法：不推荐在面试中使用，O(n²)的时间复杂度在大数据量下会超时，面试官会认为你对时间复杂度的理解不到位。
• 排序后的数组解法：属于可接受的备选方案，尤其是当题目限制不能使用哈希表时（比如考察排序相关知识点），但要主动向面试官说明排序的时间成本和是否允许修改原数组的问题。
• HashSet解法：是面试中的最优选择，时间效率最高，逻辑清晰，能体现你对哈希表特性和时间复杂度的理解。

附：两种解法的代码 #

数组解法

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        newArray = []
        for i in nums:
            if i in newArray:
                return True
            newArray.append(i)    
        return False

HashSet解法

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        hashset = set()

        for n in nums:
            if n in hashset:
                return True
            hashset.add(n)
        return False

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