- 2.23
- 以数组为链表,重复数会使链表连起来
- 和4.环形链表一致，先找相等点，再找相遇点
举个例子： nums = [1, 3, 4, 2, 2]
从下标 0 出发：nums[0] 是 1，下一步去下标 1。
从下标 1 出发：nums[1] 是 3，下一步去下标 3。
从下标 3 出发：nums[3] 是 2，下一步去下标 2。
从下标 2 出发：nums[2] 是 4，下一步去下标 4。
从下标 4 出发：nums[4] 是 2，下一步又回到了下标 2。
路径连起来就是： 0 -> 1 -> 3 -> 2 -> 4 -> [2]（循环开始了）。
你会发现，重复的数字 2，其实就是那个环的入口！
- 2.5
- 想象成链表
- 第一阶段先找相遇点（快慢指针 dowhile）
- 第二阶段找具体入口（slow 放开头，一起走，相等就是入口）
class Solution {
public int findDuplicate(int[] nums) {
// 1. 初始化快慢指针
int slow = 0;
int fast = 0;
// 2. 第一阶段：寻找相遇点
// do-while 至少执行一次，让 fast 先跑起来
do {
slow = nums[slow]; // 走一步
fast = nums[nums[fast]]; // 走两步
} while (slow != fast);
// 3. 第二阶段：寻找环入口
// slow 回到起点，fast 留在原地
slow = 0;
while (slow != fast) {
slow = nums[slow]; // 两个都走一步
fast = nums[fast];
}
// 4. 相遇点就是重复数
return slow;
}
}
slow = nums[slow];
fast = nums[nums[fast]];