数组的长度是 n+1，但是数组元素的范围是[1,n]， 构建 index -> num[index] 的有向图，设重复的数为 target，那么 nums[target] 这个位置至少会有两次被指向。

这里我也不知道怎么去证明构建的这个图一定会成环，但是可以列举一些现象：

1. 所有满足 index == nums[index] && index != target 的结点，在构建图的时候都不会参与进来。即便 index != nums[index]，这样的结点也可能不参与图的构建。

    index: 0 1 2 3 4
    item:  3 1 2 4 2
       
    index 1 和 3 的两个结点不会参与图的构建。
   

2. 数组中不存在 0 这个数字，所以位置 0 的结点一定不在环内（但可能射出去之后立地成环）。

    index: 0 1 2 .. t .. n
    item:  t _ _ .. t .. _
      
    立地成环的情况
   

由于数组中，只有一个数字出现了两次，其它数字都只出现了一次，从 nums[target] 射出去的箭头一定可以回来：

1. 如果 target = nums[target]，那么立即就回来了。
2. 否则，一定存在另一个位置的值为 target 能指向回来（假设一定能回来的话，还没想好怎么证明）。

好了，不过分纠结这个问题了，没时间去证明，现在我们假设一定有环，首先从 0 出发用快慢指针遍历，一定能进入环内。画几个图就可以发现，首次进入环的位置就是下标为 target 的位置。

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

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