LeetCode 217. Contains Duplicate 题解

LeetCode 217. Contains Duplicate 题解

题目描述

给你一个整数数组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

解题思路

方法：哈希表

思路：

• 使用哈希表来存储已经遍历过的元素
• 遍历数组，对于每个元素：
  • 如果该元素在哈希表中存在，返回true
  • 否则，将该元素加入哈希表
• 遍历结束后，返回false

复杂度分析：

• 时间复杂度：O(n)，其中 n 是数组的长度。只需要遍历数组一次。
• 空间复杂度：O(n)，需要使用哈希表来存储元素。

代码实现

方法：哈希表

class Solution: def containsDuplicate(self, nums: List[int]) -> bool: # 使用哈希表来存储已经遍历过的元素 seen = set() # 遍历数组 for num in nums: # 如果该元素在哈希表中存在，返回 true if num in seen: return True # 否则，将该元素加入哈希表 seen.add(num) # 遍历结束后，返回 false return 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

总结

本题是哈希表的经典应用问题，主要考察对哈希表思想的理解和使用。通过使用哈希表，我们可以高效地判断数组中是否存在重复元素。

哈希表的核心思想是：使用哈希表来存储已经遍历过的元素，对于每个元素，检查它是否在哈希表中存在，如果存在，返回true，否则将其加入哈希表。

这种方法不仅适用于存在重复元素问题，还可以应用于许多其他需要快速查找元素的问题。掌握哈希表的使用，对于解决这类问题非常重要。