十三 287. 寻找重复数
287. 寻找重复数https://leetcode.cn/problems/find-the-duplicate-number/
给定一个包含n + 1个整数的数组nums，其数字都在[1, n]范围内（包括1和n），可知至少存在一个重复的整数。
假设nums只有一个重复的整数，返回这个重复的数。
你设计的解决方案必须不修改数组nums且只用常量级O(1)的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]输出：2
示例 2：
输入：nums = [3,1,3,4,2]输出：3
示例 3 :
输入：nums = [3,3,3,3,3]输出：3
提示：
1 <= n <= 105nums.length == n + 11 <= nums[i] <= nnums中只有一个整数出现两次或多次，其余整数均只出现一次
进阶：
- 如何证明
nums中至少存在一个重复的数字? - 你可以设计一个线性级时间复杂度
O(n)的解决方案吗？
核心思想：把数组看成链表！
把数组看作：从索引 i 可以跳到索引 nums[i]
假设nums = [1, 3, 4, 2, 2]，索引是 0,1,2,3,4
索引: 0 1 2 3 4 数值: 1 3 4 2 2 ↓ ↓ ↓ ↓ ↓ 指向: 1 3 4 2 2 (即下一个节点的索引)从索引0开始遍历：
在索引0，值是1 → 下一步去索引1
在索引1，值是3 → 下一步去索引3
在索引3，值是2 → 下一步去索引2
在索引2，值是4 → 下一步去索引4
在索引4，值是2 → 下一步去索引2
在索引2，值是4 → 下一步去索引4
...
发现2 → 4 → 2 → 4 → 2 → 4... 成环了！
为什么一定会成环？
有 n+1 个位置，数值范围是 [1, n]
从任意位置出发，每次跳到的位置都在 [1, n] 范围内（不会跳出）
只有 n 个有效位置，但你要无限走下去，根据鸽巢原理，必然会重复访问某个位置
一旦重复访问，就形成了环！
环的入口就是答案！
路径示意：0 → 1 → 3 → 2 → 4 → 2 → 4 → 2 → 4... ↑___________| 从0出发：0 → 1 → 3 → 2 → 4 → (进入环) 环的部分：2 ↔ 4 之间循环 注意：2 是环的入口，而 2 正好就是重复的数字！既然变成了链表有环问题，就可以用经典的 Floyd 算法：
算法步骤
第一阶段：快慢指针找相遇点
慢指针每次走1步：
slow = nums[slow]快指针每次走2步：
fast = nums[nums[fast]]最终它们会在环内某点相遇
第二阶段：找环的入口
将慢指针放回起点（0）
快指针保持在相遇点
两个指针每次都走1步
再次相遇的点就是环的入口（即答案）
为什么第二阶段能找入口？（数学证明）
设：
起点到环入口距离：
a环入口到相遇点距离：
b相遇点回到环入口距离：
c
慢指针走的距离：a + b快指针走的距离：a + b + n(b + c)（n是绕的圈数）
因为快指针速度是2倍：
plain
复制
2(a + b) = a + b + n(b + c) => a + b = n(b + c) => a = n(b + c) - b = (n-1)(b+c) + c这意味着：从起点走 a 步 = 从相遇点走 c 步（绕若干圈后）
所以一个从起点走，一个从相遇点走，每次一步，相遇时就是入口！
class Solution { public int findDuplicate(int[] nums) { // 第一阶段：快慢指针找相遇点 int slow = nums[0]; int fast = nums[nums[0]]; while(slow != fast){ slow = nums[slow];// 慢指针走一步 fast = nums[nums[fast]]; // 快指针走两步 } // 第二阶段：找环的入口（即重复数） slow = 0;// 慢指针放回起点 while(slow != fast){ slow = nums[slow]; // 两个指针都走一步 fast = nums[fast]; } return slow;// 相遇点就是重复的数 } }