LeetCode 287 Find the Duplicate Number

找到一组数组中重复出现的数（只有一个），空间复杂度O(1)，时间复杂度O(n^2)以内。

其实可以看做一个链表，每个index中存储的数可以看作next指针，这样一来，如果有一个index有两个指针指向它，则链表中一定存在环。所以可以考虑使用检测链表带环的算法，即快慢指针的方法，快指针一次走两步，慢指针一次走一步。这样快慢指针先后进入环后，由于每次快一步套圈，迟早会追及。

假设a为入圈前需要走的距离，追及的地点与入圈点距离为c，还剩x重新回到入圈点，快指针比慢指针多走了n圈，那么追及的时，慢指针走了a+c而快指针走了a+c+n(x+c)（已经合并(x+c)项）。且a+c+n(x+c) = 2*(a+c)

所以a = x + (n-1)(x+c)，那么接下来让快指针也一次一步地从起点处开始出发，慢指针继续往前走，最终就能在入圈点汇合。入圈点就是我们要求的重复的数。

C++ Code

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if(nums.size() <= 1) {
            return -1;
        }
        int fast = nums[nums[0]];
        int slow = nums[0];
        while(fast != slow) {
            fast = nums[nums[fast]];
            slow = nums[slow];
        }
        
        fast = 0;
        while(fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        
        return fast;
    }
};