题目描述
思路解析动画文字版
记住这套「没见过就放进集合,见过就是答案」,下面每一帧都在套它。
开局,准备一个空集合 seen,用来记录见过的数。指针从最左边开始,一个一个往右扫。
走到第 0 个,值 3。先去集合 seen 里查一查,之前见过 3 吗？
集合里没有 3,这是第一次见到它。
把 3 记进集合,继续往后走。
走到第 1 个,值 1。先去集合 seen 里查一查,之前见过 1 吗？
集合里没有 1,这是第一次见到它。
把 1 记进集合,继续往后走。
走到第 2 个,值 2。先去集合 seen 里查一查,之前见过 2 吗？
集合里没有 2,这是第一次见到它。
把 2 记进集合,继续往后走。
走到第 3 个,值 4。先去集合 seen 里查一查,之前见过 4 吗？
集合里没有 4,这是第一次见到它。
把 4 记进集合,继续往后走。
走到第 4 个,值 6。先去集合 seen 里查一查,之前见过 6 吗？
集合里没有 6,这是第一次见到它。
把 6 记进集合,继续往后走。
走到第 5 个,值 8。先去集合 seen 里查一查,之前见过 8 吗？
集合里没有 8,这是第一次见到它。
把 8 记进集合,继续往后走。
走到第 6 个,值 3。先去集合 seen 里查一查,之前见过 3 吗？
集合里已经有 3 了！这说明 3 出现了第二次,正是那个重复 N 次的数。扫描到此结束,答案就是 3。
回头数一数,3（绿色）一共出现了 5 次,正好是题目说的那个重复 N 次的数。哈希集合让我们在第一次撞上时就锁定了它,根本不用数到底。
边界都不可怕:不管重复数撞得早还是晚,第一次撞上就收工。
两个高频追问:O(1) 空间巧解(只看后三位) + "必然存在两次近邻出现"的存在性证明。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def repeatedNTimes(self, nums: List[int]) -> int: s = set() for x in nums: if x in s: return x s.add(x)复杂度
- 时间：O(n)，最坏约扫到第 N+2 个元素(数组共 2N 个)就撞上
- 空间：O(n)，集合最多存下约 N 个不同的数
易错点
面试追问把动画讲成自己的话
追问不用额外集合,有没有 O(1) 空间的解法？
追问为什么一定存在两次出现的间隔不超过 3？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
IP 地址无效化
LeetCode 1108 · 简单 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题