LeetCode_287. Find the Duplicate Number

题目描述：

思路：根据题目描述，n+1个空间只有范围为1~n的整数，所以必定存在重复数值，题目说有且仅有一个重复数值，所以，必定存在环。这里可以设置快慢指针。

慢指针：

t=nums[0]=1

t=nums[1]=3

t=nums[3]=2

t=nums[2]=4

t=nums[4]=2

t=nums[2]=4

…

快指针：

t=nums[nums[0]]=3

t=nums[nums[3]]=4

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