LeetCode_287 尋找重複數

題目描述：

給定一個包含 n + 1 個整數的數組 nums，其數字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重複的整數。假設隻有一個重複的整數，找出這個重複的數。

示例 1:

輸入: [1,3,4,2,2]

輸出: 2

示例 2:

輸入: [3,1,3,4,2]

輸出: 3

說明：

不能更改原數組（假設數組是隻讀的）。

隻能使用額外的 O(1) 的空間。

時間複雜度小于 O(n2) 。

數組中隻有一個重複的數字，但它可能不止重複出現一次。

思路：

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