给定一个数组 nums，包含 n+1 个整数，每个整数取值范围为 [1, n]。请证明至少存在一个重复的数字。假设数组中只有一个重复的数字，求其值。

例一：
输入： [1,3,4,2,2]
输出： 2

例二：
输入： [3,1,3,4,2]
输出： 3

提示：
1. 禁止修改数组（假设数组只读）。
2. 只能使用 O(1) 的空间。
3. 时间复杂度应小于 O(n²)。
4. 数组中只有一个重复的数字，但是有可能会重复多次。

这个题还是挺有意思的。

第一眼看过去，觉得还挺容易的，我只需要拿个集合存储一下每个数字就好了，每次存之前我都检查一下是否已经包含这个数字就解决了。但是这个题还给了几个限制，不能修改原有数组，不能使用过多的空间，不能太费时，那么比较容易想到的几个方法就都用不了了。

后来看了官方给的解答，才明白这个题的本意。这个题的本质是和之前的 142. Linked List Cycle II 「环形链表 II」是一样的，即找到环形链表中环的第一个节点。但是这个想法的转换不太容易，那我用个表格解释一下。

这个表格表示了一个 {2,5,9,6,9,3,8,9,7,1} 的数组，上面一行是下标，下面一行是对应的值，在这个题中，我们要把下标的值想象为一个链表节点，把值想象成下一个节点的指针引用。这个数组就可以表示成
0->2->9->1->5->3->6->8->7->9 (开始循环)
之所以可以这么想象，是因为这个题给的条件刚好可以满足。

1. 在数组中，必然会出现重复的数字，也就是说必然有两个“节点”指向同一个节点，因为我们把值当作指针引用，值相同则指向相同，这样便必然存在环形链表；
2. 在数组中，所有的值都大于 0，不会有任何“节点”指向它，这样我们就可以把第一个值当作是链表的头节点；
3. 我们找到的环开始的“节点”可能不是第一个出现重复数字的位置，找到的链表可能不能完全包括所有的重复数字，但这个问题仅要求给出重复数字的值；
4. 我们找到的链表可能不能完全包括所有的值，但这个问题中重复的数字只有一个。

基于以上的分析，我们便可以放心的去寻找“节点”了，代码和「环形链表 II」完全相同。

/*
 * 287. Find the Duplicate Number
 * https://leetcode.com/problems/find-the-duplicate-number/
 * https://www.whosneo.com/287-find-the-duplicate-number/
 */

public class FindDuplicate {
    public static void main(String[] args) {
        FindDuplicate solution = new FindDuplicate();

        int[] nums = new int[]{1, 3, 4, 2, 2};
        System.out.println(solution.findDuplicate(nums));

        nums = new int[]{3, 1, 3, 4, 2};
        System.out.println(solution.findDuplicate(nums));
    }

    private int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;

        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        int head = 0;
        while (head != slow) {
            slow = nums[slow];
            head = nums[head];
        }

        return head;
    }
}