LeetCode 287. 寻找重复数
题目描述
题意分析
数组长度为
n + 1，每个值都在1到n之间，其中只有一种数值重复出现，返回这个重复值。它可能出现两次，也可能出现更多次；要找的是数值，不是重复位置。
n + 1次出现只能放进n种取值中，至少一种值必然重复，这就是抽屉原理。要求不能修改输入数组，只使用常数额外空间，进阶还要求线性时间。因此不能通过排序、原地标记或保存全部已见元素来规避这些限制。
解法：快慢指针找环入口
核心思路
[!blue]
把每个下标看作节点，并定义它的下一跳为
next(i) = nums[i]。由于数值都在1..n，每次读取出的值也是合法下标，可以不断沿这个映射前进。无需创建链表，数组本身已经提供了所有下一跳。从下标
0出发，路径会进入有限个节点中的某个环。没有任何数值为零，所以路径不可能返回起点0，它必定位于环外。进入环的第一个节点，既有来自环外路径的前驱，也有来自环内的前驱；这两个不同下标指向相同值，说明环入口编号就是一个重复数。题目只允许一种重复值，所以它就是答案。先用 Floyd 快慢指针找环内相遇点。慢指针每次走一步，快指针每次走两步；慢指针进入环后，快指针在环中相对它每轮多走一步，最终一定追上。初始化两者都在零时，要先移动再判断，不能把出发时的相等误当成环内相遇。
第一次相遇不一定在入口，还需要第二阶段。设起点到入口的距离为
a，环长为c，相遇时慢指针已走t步。快指针多走的t步是整圈数，因此t是c的倍数；相遇点相对入口的位置为(t - a) mod c。让相遇点再走a步，就会回到入口。因此把一个指针重置到
0，另一个留在相遇点，两者都每次走一步。经过a步，前者刚到入口，后者也回到入口；此前一个仍在环外、另一个一直在环内，不可能提前相遇。第二次相遇的编号就是重复值，直接返回即可。
解题步骤
- 令
slow = fast = 0，用数组值表示下一跳。- 先移动：
slow = nums[slow]，fast = nums[nums[fast]]；相等时结束第一阶段。- 把
slow重置到0，保持fast在相遇点。- 两者都每次走一步，直到再次相等。
- 返回相遇的编号，它就是重复的数值。
代码实现
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)$。第一阶段进入环并相遇的步数为尾长与环长之和的量级，第二阶段只走尾长；可达节点总数不超过
n + 1。- 空间复杂度：$O(1)$，只保存两个下标，不创建链表、不修改数组。
关键点总结
[!green]
- 值域落在合法下标范围内，允许把数组解释为每个节点只有一个后继的图。
- 从零出发时起点必在环外，环入口有两个不同前驱，因此对应重复值。
- 第一阶段利用不同速度相遇，第二阶段利用路程关系定位入口，职责不同。
易错点总结
[!yellow]
- 返回第一阶段相遇点，只能得到环内某个节点，未必是入口。
- 从相同的零下标初始化后先检查相等，会跳过整个找环过程；必须先移动。
- 第二阶段应回到本实现的起点
0，并让两个指针都走一步，不能沿用快指针两步的速度。- 找到入口后应返回它的编号，不是再返回
nums[入口]；入口的下一跳未必仍是重复值。- 只凭求和或异或推出一个重复值，隐含了其他取值出现次数的额外限制，本题不保证重复值只出现两次。
- 排序或原地改符号会修改输入，哈希集合会使用线性空间，都不符合本题限制。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 142. 环形链表 II | 中等 | 把数组值当作下一下标后形成函数图，重复值对应环入口，可复用快慢指针找入口。 |
| 141. 环形链表 | 简单 | 用快慢指针确定环或中间位置；本题将数组值视为后继指针寻找重复入口，该题判断链表是否存在环。 |
| 202. 快乐数 | 简单 | 用快慢指针确定环或中间位置；本题将数组值视为后继指针寻找重复入口，该题将数字变换视为隐式后继关系。 |