题目描述
思路解析
一句话答案：LeetCode 287 寻找重复数的最优解是快慢指针（Floyd 判圈）：把每个下标指向 nums 里对应的值看成链表，重复的数意味着两条边汇入同一节点、必然成环，先让快慢指针相遇，再从头同速走找到环入口，入口对应的数就是重复数。O(n) 时间、O(1) 空间，全程不修改数组。
寻找重复数的约束为什么这么苛刻
题目给一个长度为 n+1 的数组，每个元素都在 1 到 n 之间，由抽屉原理必然存在重复的数，要求把它找出来。真正定难度的是三条枷锁：不能修改原数组、只准用 O(1) 额外空间、不能上 O(n²) 暴力。三条一叠加，常规兵器几乎全部报废，这道题考的就是在夹缝里找出路。
为什么排序和哈希表都被判了死刑
先排序再找相邻相等的元素，思路没错，但排序会改动原数组，直接违反「不能修改数组」的规定。开一个哈希集合或计数数组记录出现次数，一遍扫描就能揪出重复，但那是 O(n) 的额外空间，同样超标。两层循环逐对比较倒是零空间零改动，可惜 O(n²) 被明令禁止。三条常规路全部堵死之后，只能换一个视角重新看这个数组。
数组怎么就变成了一条有环链表
关键观察：把每个下标看成一个节点，让它连一条边指向「以自己存的值为下标」的那个节点，整个数组就成了一张每个点只有一条出边的图。从下标 0 出发一路往下跳，节点有限、每步都有路可走，最终必然绕进一个圈。而「两个不同下标存着同一个值」恰好意味着两条边汇入同一个节点——被汇入的那个节点就是环的入口，它对应的数正是重复数。
还有一个细节保证从下标 0 出发是安全的：所有元素都不小于 1，没有任何边指向下标 0，所以 0 是纯粹的起点，不可能本身就困在环里。找重复数，就这样被严格翻译成了链表的「找环入口」，也就是 LeetCode 142 环形链表 II 的老问题。
快慢指针两个阶段各自在干什么
第一阶段，slow 每次跳一步（走到 nums[slow]），fast 每次跳两步。两个指针都进环之后，fast 每轮比 slow 多走一步，彼此距离每轮缩短一，不存在跳过对方的可能，所以一定会在环内某点相遇——相遇只证明有环，位置通常不是入口。
第二阶段，把 slow 拉回起点，两个指针改成同速各走一步。设起点到入口的距离为 a、入口到相遇点为 b、环长为 c。相遇时 fast 的路程恰好是 slow 的两倍，把等式化简可以得到：a 等于「从相遇点继续走到入口」的距离再加上若干整圈。于是一个从头出发、一个从相遇点出发，同速走 a 步后必然同时踩在环入口上，返回它即可。
复杂度是多少，哪里最容易写错
两个阶段的指针路程都不超过链长加环长，总时间 O(n)；全程只用 slow、fast 两个下标变量，空间 O(1)，原数组一个元素都没动，三条约束全部满足。
三个常见的坑：一是 fast 忘了写成 nums[nums[fast]]，只走一步就永远追不上 slow，死循环；二是第二阶段忘记把 slow 拉回起点，找到的不是环入口，答案直接错；三是两个指针从同一起点出发，必须先各走一步再判断相等，先判断会被起点的假相遇骗过。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
把「找重复数」翻译成「找环入口」，这是本题最妙的一步。下面一帧一帧把指针在数组上跳给你看。
slow（标 l）和 fast（标 r）都从下标 0 出发。接下来 slow 每次跳 1 步（i→nums[i]），fast 每次跳 2 步，快的去追慢的。
slow 慢慢走：从原地跳到下标 2。它每轮只走这 1 步。
fast 一口气跳 2 步（先到 2 再到 4）。它每轮比 slow 多走 1 步，所以早晚在环里追上 slow。
slow 慢慢走：从原地跳到下标 4。它每轮只走这 1 步。
fast 一口气跳 2 步（先到 7 再到 5）。它每轮比 slow 多走 1 步，所以早晚在环里追上 slow。
slow 慢慢走：从原地跳到下标 7。它每轮只走这 1 步。
fast 一口气跳 2 步（先到 1 再到 3）。它每轮比 slow 多走 1 步，所以早晚在环里追上 slow。
slow 慢慢走：从原地跳到下标 5。它每轮只走这 1 步。
fast 一口气跳 2 步（先到 8 再到 6）。它每轮比 slow 多走 1 步，所以早晚在环里追上 slow。
slow 慢慢走：从原地跳到下标 1。它每轮只走这 1 步。
fast 一口气跳 2 步（先到 8 再到 6）。它每轮比 slow 多走 1 步，所以早晚在环里追上 slow。
slow 慢慢走：从原地跳到下标 3。它每轮只走这 1 步。
fast 一口气跳 2 步（先到 8 再到 6）。它每轮比 slow 多走 1 步，所以早晚在环里追上 slow。
slow 慢慢走：从原地跳到下标 8。它每轮只走这 1 步。
fast 一口气跳 2 步（先到 8 再到 6）。它每轮比 slow 多走 1 步，所以早晚在环里追上 slow。
slow 慢慢走：从原地跳到下标 6。它每轮只走这 1 步。
fast 跳 2 步落到下标 6，正好踩在 slow 身上——两人相遇了！相遇点在环里（不一定是入口）。
相遇之后做一个关键操作：slow 拉回下标 0，fast 留在相遇点 6。现在两人改成同样速度（各走 1 步）一起走——它们会在「环入口」重逢，那就是答案。
两人各走 1 步：slow 到 2、fast 到 8。同速前进，直到再次相遇。
两人各走 1 步：slow 到 4、fast 到 6。同速前进，直到再次相遇。
两人各走 1 步：slow 到 7、fast 到 8。同速前进，直到再次相遇。
两人各走 1 步：slow 到 5、fast 到 6。同速前进，直到再次相遇。
两人各走 1 步：slow 到 1、fast 到 8。同速前进，直到再次相遇。
两人各走 1 步：slow 到 3、fast 到 6。同速前进，直到再次相遇。
两个指针同时落在下标 8，重逢！这个下标就是环入口，它的「下标值」8 正是那个重复的数字。
绿色高亮的下标 8 就是环入口，重复数 = 8。回头看：我们把数组当链表跳了一圈，从没改过它一个元素，额外只用两个指针，O(n) 时间、O(1) 空间，两条枷锁全解开。
无论重复出现几次、在哪个位置，环入口都唯一，算法都成立。
两个高频追问：① 重复数 ⇔ 有环的原理；② 放开约束后的替代解，反衬本解之巧。
参考代码
def findDuplicate(nums): slow = fast = 0 # 阶段一：快慢指针在环里相遇 while True: slow = nums[slow] # 慢走 1 步 fast = nums[nums[fast]] # 快走 2 步 if slow == fast: break # 阶段二：slow 回起点，齐步走找环入口 slow = 0 while slow != fast: slow = nums[slow] fast = nums[fast] return slow # 环入口 = 重复数复杂度
- 时间：O(n)，两阶段指针各最多走环长 + 链长，合计线性
- 空间：O(1)，只用 slow、fast 两个下标变量，不开哈希/不改数组
易错点
面试追问把动画讲成自己的话
追问为什么「有重复数」就等于「图里有环」？
追问如果允许修改数组或用额外空间，有没有更简单的解？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
LRU 缓存
LeetCode 146 · 中等 · 沿着 链表 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题