数组哈希集合去重
LC217 · 存在重复元素
给定一个整数数组 nums，如果任意值出现至少两次，返回 true；如果每个元素都不同，返回 false。
这题不是让你找出所有重复数字，而是只要判断“有没有重复”。
示例
输入 nums = [1,2,3,1]
输出 true
解释：数字 1 出现了两次。
step 1
为什么暴力比较慢
先展示暴力法：每个数字都和后面的数字比较，时间复杂度 O(n²)。
如果数组很长，前面的数字会反复回头找很多次；比较次数会像双层循环一样增长。
step 2
为什么用 set
不回头反复比较，而是把已经见过的数字放进 set。
每次扫描新数字，只问一句：它以前出现过吗？
core idea
核心概念区：set 是登记册
set 是“已见过数字登记册”
不记录出现次数
只关心某个数字是否出现过
Go 里可以用 map[int]struct{} 模拟 set
animation
动画实验台：传送带 + 安检登记台
第 1 / 10 步
左侧：数组传送带 [1,2,3,1]i 准备就位
1
0
2
1
3
2
1
3
中间：当前扫描指针 i / 检查口
等待第一个数字进入检查口
右侧：set 登记册set = {}
空登记册
当前步骤说明
初始化：数组 [1,2,3,1] 出现，set = {}
从左到右扫描数组，set 记录已经见过的数字。
动画：传送带就位，右侧 set 登记册还是空的。
Go 代码同步高亮
01func containsDuplicate(nums []int) bool {02 seen := make(map[int]struct{})0304 for _, num := range nums {05 if _, ok := seen[num]; ok {06 return true07 }08 seen[num] = struct{}{}09 }1011 return false12}
solution
Go 题解区
Go 代码同步高亮
01func containsDuplicate(nums []int) bool {02 seen := make(map[int]struct{})0304 for _, num := range nums {05 if _, ok := seen[num]; ok {06 return true07 }08 seen[num] = struct{}{}09 }1011 return false12}
第 2 行 · 初始化 set 登记册
seen := make(map[int]struct{}) 高亮时，右侧 set 登记册初始化为空。
第 5 行 · 查询登记册
if _, ok := seen[num]; ok 高亮时，动画表现为“查询登记册”。ok 为 true 就说明以前见过。
第 6 行 · 重复命中，提前结束
return true 高亮时，动画表现为“重复命中，提前结束”。不用再看后面的数字。
第 8 行 · 加入登记册
seen[num] = struct{}{} 高亮时，动画表现为“加入登记册”。struct{}{} 只占集合位置，不额外表达次数。
第 11 行 · 扫完没命中
return false 高亮时，用另一个输入 [1,2,3,4] 展示“扫完没命中”。
return false 分支：输入 [1,2,3,4]
1234
扫完没命中，最后高亮 return false。
invariant
正确性解释
不变量：扫描到 nums[i] 之前，set 中保存的是 nums[0...i-1] 里所有出现过的数字。
如果 nums[i] 在 set 中，说明它之前出现过，返回 true。
如果 nums[i] 不在 set 中，把它加入 set，继续扫描。
如果扫描完还没有命中，说明不存在重复元素。
cost
复杂度区
时间复杂度 O(n)：每个数字只扫描一次。
空间复杂度 O(n)：最坏情况下所有数字都不同，set 要保存 n 个数字。
pitfalls
常见误区区
- 1.命中重复后不需要继续扫。
- 2.set 不是记录次数，只记录是否出现过。
- 3.map[int]bool 可以写，但 map[int]struct{} 更像集合，且不额外存 bool。
- 4.排序也能做，但会改变数组顺序，时间复杂度通常是 O(n log n)。
interview
面试回答区
30 秒回答模板
这题我会用哈希集合。遍历数组时，用 set 记录已经出现过的数字。每次遇到一个数字，先判断它是否已经在 set 中。如果在，说明重复出现，直接返回 true。如果不在，就加入 set。遍历结束还没有发现重复，就返回 false。时间复杂度 O(n)，空间复杂度 O(n)。