为什么在这个重复整数问题中 HashSet 比数组更快？

Question

我刚开始学习数据结构和算法，正在开始做 NeetCode 150 题。我遇到的第一个问题并不困难，我理解它为什么有效，但我很好奇为什么最好的解决方案涉及使用 HashSet 而不是数组。

我确信这又回到了时间复杂度，这是一个我很难掌握的主题，所以我希望有人能给我一个简单的细分，说明为什么一种解决方案比另一种更好，以及是否会更好在这里使用数组而不是 HashSet 真的很糟糕（如果我在面试中使用它，他们会不喜欢它）。

这是我想出的解决方案。除了使用数组和 .append() 而不是 HashSet 和 .add() 之外，它几乎完全相同。该解决方案在技术上是正确的，但根据我所做的研究，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

这是实际的最佳解决方案。

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

有什么区别？另外，添加 nums.sort() 对第一种方法会有什么影响？这会以任何方式改变运行时间吗？抱歉，如果这些问题非常明显，我只需要一些帮助我理解这些概念。

Answer 1

让我们检查一下

in

语句中

if

运算符的使用。

对于数组，

in

操作是一个 O(n) 操作 - 顺序搜索数组元素，在最坏的情况下（即，如果正在搜索的项不在数组中），它会遍历所有元素它的。对于哈希集，

in

操作是一个 O(1) 操作 - 对有问题的项进行哈希处理，并对照哈希的正确存储桶进行检查（注意：这假设哈希算法是合理的，对于以下情况应该是整数）。