华为 OD 训练营 · 题解精讲
LC217. 存在重复元素
LC217. 存在重复元素 视频地址。
题目描述
给你一个整数数组 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^5 -10^9 <= nums[i] <= 10^9
题目解析
解题思路
题目要求判断数组中是否存在重复元素。参考代码采用哈希集合（HashSet） 来记录已经遍历过的数字，利用集合的 O(1) 查找特性，在遍历过程中检查当前数字是否已经出现过。
核心思想：维护一个集合 pre，初始为空。遍历数组中的每个数字 num，如果 num 已经在集合中，说明出现了重复，直接返回 true；否则将 num 加入集合。若遍历结束都没有发现重复，则返回 false。
关键步骤
1. 初始化空集合 pre = set() 2. 遍历数组：对每个 num in nums：
- 检查
num in pre：若存在 → 返回true - 否则将
num加入pre
3. 遍历结束 → 返回 false
示意图（以 [1,2,3,1] 为例）：
初始: pre = {}
遍历:
num=1: 1 not in {} → pre = {1}
num=2: 2 not in {1} → pre = {1,2}
num=3: 3 not in {1,2} → pre = {1,2,3}
num=1: 1 in {1,2,3} → return True复杂度分析
- 时间复杂度：O(n)，其中 n 为数组长度。每个元素只被遍历一次，集合的插入和查找操作平均为 O(1)。
- 空间复杂度：O(n)，最坏情况下（无重复元素）需要存储所有 n 个元素。
参考代码
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
# 使用数据结构 set 来存放 nums 里面的所有数字
pre = set()
# 遍历数组
for num in nums:
# 如果数字已经存在于 set 中，直接返回 true
if num in pre:
return True
# 把元素添加到 set 中
pre.add(num)
# 如果成功遍历完数组，则表示没有重复元素，返回 false
return False