287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

思路

可以考虑用环形链表的思路

[1,n]区间，没有索引0，所以环的入口不可能在index=0,所以起点一定不在环中。 所以当出现环时 环的入口就为重复的元素

如上图，slow 和 fast 会在环中相遇，先假设一些量：起点到环的入口长度为 m，环的周长为 c，在 fast 和 slow 相遇时 slow 走了 n 步。则 fast 走了 2n 步，fast 比 slow 多走了 n 步，而这 n 步全用在了在环里循环（n%c==0）。 当 fast 和 last 相遇之后，我们设置第三个指针 finder，它从起点开始和 slow(在 fast 和 slow 相遇处)同步前进，当 finder 和 slow 相遇时，就是在环的入口处相遇，也就是重复的那个数字相遇。

为什么 finder 和 slow 相遇在入口
fast 和 slow 相遇时，slow 在环中行进的距离是 n-m，其中 n%c0。这时我们再让 slow 前进 m 步——也就是在环中走了 n 步了。而 n%c0 即 slow 在环里面走的距离是环的周长的整数倍，就回到了环的入口了，而入口就是重复的数字。 我们不知道起点到入口的长度 m，所以弄个 finder 和 slow 一起走，他们必定会在入口处相遇。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        
        int fast = 0, slow = 0;
        while(true){
            fast = nums[nums[fast]];
            slow = nums[slow];
            if(fast == slow)
                break;
        }
        int finder = 0;
        while(true){
            finder = nums[finder];
            slow = nums[slow];
            if(slow == finder)
                break;        
        }
        return slow;
    }
};