脑筋急转弯+链表找环

我们按照数组的每个下标和下标存储的数来建图，如图：

题目保证了一定由重复的数，即一定有数组的两个位置存储该数，即一定有两个点指向该点,则一定存在环。

根据上面的分析，该题转换成了找链表环的入口问题。

$ 时间复杂度O(N),空间复杂度O(1)$

参考文献

lc究极班

AC代码

class Solution {
public:
    int findDuplicate(vector<int>& ne) {
        int s = 0 , f = 0;
        while (true){//因为一定存在环，所以不会死循环
            f = ne[f];
            s = ne[s];
            f = ne[f];
            if (f == s){
                s = 0;
                while (s != f) s = ne[s], f = ne[f];
                return f;
            }
        }
    }
};