存在重复元素

难度: Easy

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true

示例 2：

输入：nums = [1,2,3,4]
输出：false

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

提示：

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Submission

运行时间: 31 ms

内存: 29.3 MB

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        s=set()
        for num in nums:
            if num in s:
                return True
            else:
                s.add(num)
        
        return False

Explain

这个题解的思路是使用哈希表来判断数组中是否存在重复元素。具体做法是：遍历数组，对于每个元素，如果它已经在哈希表中出现过，说明找到了重复元素，直接返回 True；如果没有出现过，就将该元素加入哈希表中。如果遍历完整个数组都没有找到重复元素，返回 False。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        s = set()  # 创建一个空的哈希表
        for num in nums:  # 遍历数组中的每个元素
            if num in s:  # 如果当前元素已经在哈希表中出现过
                return True  # 说明找到了重复元素，直接返回 True
            else:
                s.add(num)  # 如果当前元素没有出现过，将其加入哈希表中
        
        return False  # 遍历完整个数组都没有找到重复元素，返回 False

Explore

哈希表（或集合）提供了平均时间复杂度为 O(1) 的查找、插入和删除操作，这使得它在处理存在重复元素的问题时非常高效。对于这道题目，我们需要快速判断一个元素是否已经存在于集合中，而哈希表正好提供了这一功能。使用数组或链表虽然也能解决问题，但它们在查找操作上的时间复杂度最坏为 O(n)，对于大规模数据处理会较为低效。因此，哈希表是解决这一问题的最佳数据结构。

处理大量数据时，哈希表可能遇到的主要性能瓶颈包括哈希冲突和动态扩容。哈希冲突是由于不同的键映射到同一个哈希值导致的，这会增加查找和插入操作的时间复杂度。动态扩容发生在哈希表填充元素接近容量极限时，需要重新分配更大的内存空间并重新哈希所有现有元素，这个过程中的时间和空间开销较大。此外，大量数据也可能导致较高的内存占用。

对于非常小的输入数组，这种方法的性能非常高效，因为操作的元素少，哈希表的操作几乎可以认为是常数时间。对于非常大的输入数组，尽管单次操作的时间复杂度仍是 O(1)，但总体性能可能会受到前述的哈希冲突和动态扩容影响。尽管如此，相较于其他线性时间查找的方法，使用哈希表通常仍然更加高效。

在当前的算法中，如果`num`已经在`set`中，直接返回`True`是最优的处理方式，因为我们的目标是检测数组中是否存在重复元素。一旦发现重复元素，立即终止进一步的查找和处理可以节省时间，避免不必要的操作。此外，这种方法已经是基于哈希表操作的最优解法，不存在更多的时间复杂度上的优化空间。如果考虑空间优化，可以使用更复杂的数据结构，但这通常会以牺牲时间效率为代价。