快慢指针

O(1)空间，O(n)时间：

public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        int sum = 0, n = 0;
        for(n = 0; n < length; ++n) sum += numbers[n];    //无重复就是等差求和
        if(sum == n*(n - 1)/2){
            duplication[0] = -1;
            return false;
        }
        //把下标当成next指针，数组变成链表，求环的入口
        int i = numbers[numbers[0]], j = numbers[numbers[numbers[0]]];//快慢指针
        while(i != j){    //指针i和j相遇时，j走了i的两倍，且j多走了任意个环
            i = numbers[i];    //指针i每次下移一个节点
            j = numbers[numbers[j]];    //指针j每次下移2个节点
        }
        int k = numbers[0];    //指针i已经走了任意个环，之后仍在环上转
        while(i != k){    //i与k一起走，必在环的入口相遇
            i = numbers[i];
            k = numbers[k];
        }
        duplication[0] = i;
        return true;
    }
}