Python算法训练序列

数组与哈希 · Unit 01

217
LeetCode 217Contains Duplicate · 存在重复元素

看到一个元素时，
怎样立刻知道它以前来过？

先体验重复扫描的代价，再构造“已见元素”集合。代码阶段允许随时查看参考答案，并可逐行播放 Python 代码与数组、变量和集合的同步变化。

LeetCode #217 原题内容 中文转述 · 保留示例、约束与提交签名

题目要求

给定一个整数数组 nums。只要数组中存在某个数至少出现两次，就返回 True；如果每个元素都只出现一次，则返回 False。

class Solution: def containsDuplicate(self, nums: List[int]) -> bool: # 在这里提交答案

约束

  • 1 ≤ len(nums) ≤ 100000
  • -10⁹ ≤ nums[i] ≤ 10⁹

官方示例

nums = [1, 2, 3, 1]
输出：True
原因：1 在索引 0 和 3 出现。
nums = [1, 2, 3, 4]
输出：False
原因：所有元素互不相同。
nums = [1,1,1,3,3,4,3,2,4,2]
输出：True
1. 暴力搜索
2. 发现瓶颈
3. 构造 seen
4. 代码联动
5. 小型迁移
系统记忆区
当前没有保存任何元素
当前索引 i0
当前 num—
比较/查询次数0
函数状态运行前
先尝试补全卡住可直接看答案
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
seen =
for num in nums:
if :
return True
return False
class Solution: def containsDuplicate(self, nums: List[int]) -> bool: seen = set() for num in nums: if num in seen: return True seen.add(num) return False
答案确实可以很短。上面是适合学习和动画化的显式版本：它能提前返回，并清楚展示 seen 的变化。Python 还可以写成一行：return len(nums) != len(set(nums))，但一行版会隐藏循环、不变量和提前结束过程。
代码—图像联动动画可点击任意代码行
1class Solution:
2 def containsDuplicate(self, nums: List[int]) -> bool:
3 seen = set()
4 for num in nums:
5 if num in seen:
6 return True
7 seen.add(num)
8 return False
点击“下一行”，观察代码状态怎样映射到数组和 seen。
完成代码联动后进入下一阶段 完成任一条件即可解锁：代码补全正确、查看参考答案，或播放到轨迹最后一步。

迁移题：返回第一个重复值

输入 [5, 1, 3, 2, 3, 5]，返回扫描过程中遇到的第一个重复值。沿用同一个 seen 不变量。

本单元形成的算法Skill

当问题不断询问“当前对象以前是否出现过”时，用集合压缩已经处理过的历史。循环不变量是：处理当前 num 前，seen 恰好包含此前扫描到的不同元素。

LeetCode #217Python set时间 O(n)空间 O(n)代码与状态同步
#217 当前：哈希集合Contains Duplicate
#1 下一单元：哈希映射Two Sum
#242 频次统计Valid Anagram
#49 按键分组Group Anagrams