LeetCode 287. 寻找重复数
目录
题目描述
题意分析
给定一个长度为
n + 1的数组，每个元素的取值都落在[1, n]这个闭区间内，要求把那个重复出现的数字找出来并返回。有三条约束几乎直接决定了做法，值得逐条拆开看。
第一条是「
n + 1个数、取值只有n种」。这是一个数量上的强信号：抽屉不够用，重复一定存在，所以不需要考虑「找不到答案」的分支。第二条是「只有一个数字重复，但它可能重复不止一次」。也就是说答案唯一，但出现次数不定，可能是
[1, 3, 4, 2, 2]这种出现两次，也可能是[2, 2, 2, 2, 2]这种占满整个数组。任何依赖「重复元素恰好出现两次」的技巧（比如异或消元、求和作差）在这里都会失效。第三条是进阶要求：不能修改数组，且只能用常数级额外空间。这一条把最顺手的两类做法都挡在门外——排序会破坏原数组，哈希表或计数数组要吃掉 $O(n)$ 空间。
边界方面还要留意：
n最小可以是 1，此时数组为[1, 1]；数组元素取值不含0，所以下标0这个位置永远不会被任何元素「指向」，这一点后面会变成解法的关键支点。
解法：快慢指针找环入口
核心思路
问题关键：数组不能修改，额外空间又要求 $O(1)$，排序、哈希表和原地标记都不合适。突破口是元素值都在
[1, n]：每个值都能作为下标，于是可把i -> nums[i]看成一条有向边。从下标
0开始反复执行next = nums[next]。路径只有有限个位置可走，必然重复并进入环。设路径中第一个重复到达的节点为d，它在路径上有两个不同前驱；而节点v的入度就是数值v在数组中的出现次数。题目只有一个重复数，所以d正是重复数，也是环入口。为什么选 Floyd：问题已经转成“链表找环入口”，快慢指针能在线性时间、常数空间内完成，且不改数组。值域二分也满足空间要求，但每轮都要扫描数组，时间是 $O(n \log n)$，只适合作为备选。
不变量与正确性：第一阶段中，慢指针每轮走 1 步，快指针走 2 步；进入环后，快指针相对慢指针每轮前进 1 步，因此一定相遇。设起点到入口距离为
a，入口到相遇点距离为b，环长为c。相遇时两者路程差是整圈，得到a + b ≡ 0 (mod c)，即从相遇点到入口的距离与a同余。把一个指针放回0，两者每次各走一步，下一次相遇点必是环入口，也就是重复数。
解题步骤
面试时可按下面 4 步口述：
- 把数组解释为函数图：下标
i指向nums[i]。- 从
0出发，慢指针走一步、快指针走两步，直到在环内相遇。- 将慢指针重置到
0，快指针留在相遇点；两者改为每次都走一步。- 再次相遇的位置就是环入口，返回该下标。
以
[1,3,4,2,2]为例，路径是0 -> 1 -> 3 -> 2 -> 4 -> 2 ...。第一阶段相遇在4；一个指针回到0后同步前进，最终在入口2相遇，因此重复数是2。
代码实现
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
func findDuplicate(nums []int) int {
slow, fast := 0, 0
for {
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast {
break
}
}
slow = 0
for slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow
}
复杂度分析
- 时间复杂度：$O(n)$。两个阶段的移动次数都不超过链长与环长的常数倍。
- 空间复杂度：$O(1)$。只使用两个指针，且不修改输入数组。
关键点总结
- “值域落在合法下标范围内”是把数组转换成函数图的信号。
- 重复数对应入度大于 1 的节点；从
0出发的路径第一次重复处就是环入口。- Floyd 第一阶段只保证在环内相遇，第二阶段才定位入口。
- 若面试中暂时想不到 Floyd，可先给出值域二分的 $O(n \log n)$ 解法，再说明如何优化到线性时间。
易错点总结
- 第一阶段的相遇点不一定是答案。
[1,3,4,2,2]中相遇点可为4，入口才是2。- 第二阶段必须把一个指针重置到下标
0，并让两个指针都改为每次走一步。- 两个指针若都初始化为
0，不能先判断相等再移动；Java 用do-while，Go 用先移动后判断的无限循环。- 异或或求和只适用于重复次数受限的模型，本题重复数可能出现多次。
- 排序、哈希表、负号标记虽能找出答案，但分别违反“不修改数组”或“常数额外空间”的要求。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 141. 环形链表 | 简单 | 只判断环是否存在，不必求入口，是 Floyd 的第一阶段 |
| 142. 环形链表 II | 中等 | 真链表上求环入口，本题第二阶段的原型 |
| 202. 快乐数 | 简单 | 环由数位平方和函数隐式生成，需判断环是否落在 1 上 |
| 457. 环形数组是否存在循环 | 中等 | 每个下标都要当起点试一遍，且环需方向一致、长度大于一 |
| LCR 022. 环形链表 II | 中等 | 142 的同题改编，可与哈希记录法对照复习 |
| 面试题 02.08. 环路检测 | 中等 | 同为求环入口，常被追问 $O(1)$ 空间与哈希解法的取舍 |
| 442. 数组中重复的数据 | 中等 | 允许修改数组，用正负号标记的原地哈希找出全部重复元素 |
| 645. 错误的集合 | 简单 | 同时求重复数与缺失数，考察值与下标的双向映射 |