287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums*，其数字都在 1 到 *n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

解法

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int tortoise = nums[0], hare = nums[0];
        do{
            tortoise=nums[tortoise];
            hare=nums[nums[hare]];
        } while(tortoise!=hare);

        tortoise=nums[0];
        while(tortoise!=hare){
            tortoise=nums[tortoise];
            hare=nums[hare];
        }
        return hare;
    }
};