找卧底 解题报告

由于数组中的数的范围是[1,n]，而且只有两个相同的数，那么就可以转化为判断这个链表中是否有环，然后找环的入口，举个例子：有5个数字[2, 4, 3, 1, 2]，那么我们可以建立如下的映射关系：
下标0 -> 2
下标1 -> 4
下标2 -> 3
下标3 -> 1
下标4 -> 2
那么我们从下标0出发，根据a[i]算出一个数，以此类推，我们可以得到如下的序列：
0->2->3->1->4->2
那么在上述序列中就存在一个环路，是2->3->1->4->2，所以我们可以通过快慢指针来找环的入口即可。
代码如下:

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int search(int n, vector<int>& a) {
        // write code here
        int slow = 0, fast = 0;
        while(1) {
            fast = a[a[fast]];
            slow = a[slow];
            if(fast == slow) {
                fast = 0;
                while(a[slow] != a[fast]) {
                    fast = a[fast];
                    slow = a[slow];
                }
                return a[slow];
                //return a[slow];
            }
        }
    }
};