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否则将其加入哈希表。这种方法不仅适用于存在重复元素问题还可以应用于许多其他需要快速查找元素的问题。掌握哈希表的使用对于解决这类问题非常重要。