题目描述

解题思路

参照：https://leetcode.cn/problems/find-the-duplicate-number/solution/287xun-zhao-zhong-fu-shu-by-kirsche/
本题就是环形链表II的数组抽象出来的，我们要判断哪个数字重复，那么我们类比为链表，此时

重复的数组可以构成环，所以可以类比环形链表来求出这个环的入口。
注意公式在环形链表II中推导过，此外题目给的数字是[1,n]所以不会一开始就进入环，所以不会死循环。

难得是类比过去。

public int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[nums[0]];
    // 进入环
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    // 找到环的入口
    int pre = 0;
    int cur = slow;
    while (pre != cur) {
        pre = nums[pre];
        cur = nums[cur];
    }
    return pre;
}