题目描述
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内。
可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，请你找出这个重复的数。
并且题目通常还会附带两个限制：
-
不能修改原数组
-
只用
O(1)的额外空间
示例分析
示例 1
输入: nums = [1,3,4,2,2]
输出: 2
因为数字 2 出现了两次，所以答案是 2。
示例 2
输入: nums = [3,1,3,4,2]
输出: 3
因为数字 3 出现了两次，所以答案是 3。
解题思路
这道题最巧妙的地方在于：
它看起来是数组题，但其实可以转化成链表判环题。
你给出的代码正是这道题最经典的做法： Floyd 判圈算法（快慢指针）。
代码如下：
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
int pre1 = 0;
int pre2 = slow;
while(pre1 != pre2){
pre1 = nums[pre1];
pre2 = nums[pre2];
}
return pre1;
}
}
虽然代码不长，但这题真正难的是：
-
为什么数组能看成链表
-
为什么一定会有环
-
为什么环的入口就是重复数字
-
为什么相遇后再走一次就能找到入口
下面一步一步讲清楚。
为什么数组可以看成链表
我们先观察题目的条件：
-
数组长度是
n + 1 -
数组中的每个数字都在
[1, n]范围内
这意味着什么？
意味着对于每一个下标 i，都可以把：
i -> nums[i]
看成一条“指向下一个位置”的边。
也就是说，我们可以把数组下标当作节点，把 nums[i] 当作“下一个节点”。
例如：
nums = [1,3,4,2,2]
下标和值关系如下：
-
0 -> 1 -
1 -> 3 -
2 -> 4 -
3 -> 2 -
4 -> 2
如果把它画出来，就是：
0 -> 1 -> 3 -> 2 -> 4
^ |
|_________|
你会发现，这里面出现了一个环：
2 -> 4 -> 2
所以这个问题就变成了：
在这样一张“链式结构”里，找到环的入口。
而环的入口对应的，就是重复数字。
为什么一定会有环
这其实和抽屉原理有关。
数组一共有 n + 1 个位置，但数字只能取 [1, n] 这 n 个值。
也就是说：
-
有
n + 1个节点 -
但“下一跳”只能跳到
1 ~ n这些位置
这样必然会有至少两个不同的位置，指向同一个数字。 于是整条路径在不断往前走的过程中，就一定会进入一个环。
所以这题一定可以用判环的思路做。
为什么环的入口就是重复数字
这是这道题最关键的一点。
因为重复数字的本质就是：
有至少两个不同的下标，都指向同一个值。
比如：
nums = [1,3,4,2,2]
其中：
-
nums[3] = 2 -
nums[4] = 2
说明：
-
下标
3指向2 -
下标
4也指向2
于是节点 2 就成了“多条路径汇合”的位置。
而在链式结构里，这种“汇合”最终会形成一个环。 这个汇合点，也正是环的入口。
所以：
找到环的入口，就等于找到了重复数字。
Floyd 判圈算法在这里怎么用
Floyd 判圈算法通常分两步：
第一步：先让快慢指针相遇
-
慢指针一次走一步
-
快指针一次走两步
如果有环，它们一定会在环中某个位置相遇。
第二步：再找环的入口
-
一个指针从起点重新出发
-
一个指针从第一次相遇点出发
-
两个指针都一次走一步
它们最终会在环的入口相遇。
而这道题里，环的入口就是重复数。
代码解析
1. 定义快慢指针
int slow = 0;
int fast = 0;
一开始两个指针都从下标 0 出发。
这里之所以从 0 出发，是因为 0 本身不在 [1, n] 的取值范围内，它相当于整条链的一个“起点”。
2. 先走一步，避免初始就相等
slow = nums[slow];
fast = nums[nums[fast]];
这一步表示：
-
slow先走一步 -
fast先走两步
因为如果一开始就直接进入 while (slow != fast)，那它们初始都为 0，会立刻相等，逻辑就不对了。
所以先让它们走起来。
3. 第一阶段：在环中相遇
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
-
slow = nums[slow]：一次走一步 -
fast = nums[nums[fast]]：一次走两步
因为存在环，所以快慢指针最终一定会在环中相遇。
这一步的作用只是确认“有环”，并拿到环中的某个相遇点。
4. 第二阶段：寻找环入口
int pre1 = 0;
int pre2 = slow;
此时：
-
pre1从起点0出发 -
pre2从第一次相遇点出发
然后两个指针都每次走一步：
while(pre1 != pre2){
pre1 = nums[pre1];
pre2 = nums[pre2];
}
最终它们会在环的入口相遇。
5. 返回入口
return pre1;
因为环的入口就是重复数字，所以直接返回即可。
为什么第二次相遇点就是环入口
这是这道题最容易卡住的地方。
我们设：
-
从起点到环入口的距离是
a -
从环入口到第一次相遇点的距离是
b -
环的长度是
c
当快慢指针第一次相遇时：
-
慢指针走了
a + b -
快指针走了
a + b + k * c
又因为快指针速度是慢指针的两倍，所以：
2(a + b) = a + b + k * c
整理得：
a + b = k * c
进一步可得：
a = k * c - b
这说明：
从起点走到环入口的距离，等于从相遇点继续往前走到环入口的距离（绕若干圈后）。
所以：
-
一个指针从起点出发
-
一个指针从相遇点出发
-
每次都走一步
它们一定会在环入口相遇。
而环入口就是重复数。
示例推演
我们还是看：
nums = [1,3,4,2,2]
对应关系：
-
0 -> 1 -
1 -> 3 -
3 -> 2 -
2 -> 4 -
4 -> 2
链式结构：
0 -> 1 -> 3 -> 2 -> 4
^ |
|____|
环入口是 2。
第一阶段：快慢指针相遇
初始：
slow = nums[0] = 1
fast = nums[nums[0]] = nums[1] = 3
继续走：
-
slow = nums[1] = 3 -
fast = nums[nums[3]] = nums[2] = 4
继续走：
-
slow = nums[3] = 2 -
fast = nums[nums[4]] = nums[2] = 4
继续走：
-
slow = nums[2] = 4 -
fast = nums[nums[4]] = nums[2] = 4
此时相遇在 4。
第二阶段：找入口
现在：
-
pre1 = 0 -
pre2 = 4
同时每次走一步：
第一步：
-
pre1 = nums[0] = 1 -
pre2 = nums[4] = 2
第二步：
-
pre1 = nums[1] = 3 -
pre2 = nums[2] = 4
第三步：
-
pre1 = nums[3] = 2 -
pre2 = nums[4] = 2
相遇在 2。
所以答案就是：
2
为什么不能直接排序或哈希表
很多同学第一次做这题时，可能会想到：
方法一：排序
-
先排序
-
再看哪个数和前一个数相同
这种方法当然能找出来，但会修改原数组，不符合题目要求。
方法二：哈希表 / HashSet
-
一边遍历，一边记录出现过的数
-
再次出现时返回
这种方法也能做出来，但空间复杂度是 O(n)，不符合题目要求的 O(1) 额外空间。
所以这道题真正厉害的地方就在于：
既不改数组，又只用常数空间。
而这正是 Floyd 判圈算法的优势。
复杂度分析
设数组长度为 n + 1。
时间复杂度
O(n)
快慢指针的两轮移动都是线性的，所以总时间复杂度是 O(n)。
空间复杂度
O(1)
只用了有限几个指针变量，没有额外使用数组、哈希表等结构。
这道题为什么这么经典
这道题是 LeetCode 里非常有代表性的一道“思维转换题”。
因为它表面上是数组题，但实际上考的是：
-
如何把数组抽象成链表
-
如何把重复数问题转成找环入口问题
-
如何灵活使用 Floyd 判圈算法
所以这题真正难的不是代码，而是：
能不能想到这种转换。
一旦你把“数组下标 -> 数组值”的映射关系看成链表，这题就会豁然开朗。
总结
这道题的核心可以总结成三步：
-
把数组看成一条链表，其中
i -> nums[i] -
因为有重复数字，所以这条链一定有环
-
你可以把这题记成一句话：
寻找重复数，本质就是在数组构成的隐式链表中寻找环入口。
这是一道非常经典、也非常巧妙的题。 只要把“数组转链表”“重复数=环入口”这两个关键点想明白，代码反而是顺理成章的。
