287 . 寻找重复数（中等）
方法 快慢指针
思路
-
要解决这道题首先要理解如何将输入的数组看作为链表。对于数组 nums 中的数字范围在 [1, n]，考虑两种情况：
-
如果数组中没有重复的数字，以
[1, 3, 4, 2]为例，将数组下标 n 和 nums[n] 建立映射关系f(n)，即 n->f(n)：0->1, 1->3, 2->4, 3->2，从下标 0 出发， 根据 f(n) 计算出一个值，以这个值为新的下标，依次类推，直到下标越界，这样产生了一个类似链表的序列：0->1->3->2->4->null； -
如果数组中有重复的数字，以
[1, 3, 4, 2, 2]为例， 其映射关系为 n->f(n)：0->1, 1->3, 2->4, 3->2, 4->2，此时的“链表序列”为：0->1->3->2->4->2->...，出现了循环2->4->2->4->...，如下图所示。
-
-
因此，如果数组中出现重复的数字，那么就一定会产生多对一的映射，所以“链表序列”一定会有“环”。综上，数组中有重复的整数 <=> 数组中存在环，找到数组中重复的整数 <=> 找到链表中的环入口。
-
针对这类型的题目，就需要使用快慢指针，慢指针走一步，快指针走两步，即
slow = nums[slow]，fast = nums[nums[fast]]。 -
当 slow == fast 时，二者走到相遇点，记为 y 。将环的入口点记为 x ，链表起始点记为 h，设 链表起始点 h 到 x 的距离为 a， x 到 y 的距离为 b 。
-
由于 “慢指针走过的距离是快指针的一半” ，则有
2 * (a + b) = a + b + (y 到 x 的距离) + b，因此 y 到 x 的距离就等于 0 到 x 的距离 【注意：这里的 y 到 x 的距离可能走了很多圈】。此时再设置两个新指针，一个从 0 出发，一个从相遇点 y 出发，两个指针相遇的地方即为 环的入口点 x 。
代码
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0, fast = 0;
// 找到相遇点
do{
slow = nums[slow];
fast = nums[nums[fast]];
}while(slow != fast);
// 找到起始点
// 起始点->环的起点 = 环的起点->相遇点
int pre1 = 0, pre2 = slow;
while(pre1 != pre2){
pre1 = nums[pre1];
pre2 = nums[pre2];
}
return pre1;
}
};
