###### tags: `LeetCode` `Medium`
# LeetCode #287 [Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)
### (Medium)
給定一個包含 n + 1 個整數的數組 nums ，其數字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重複的整數。

假設 nums 只有 一個重複的整數 ，找出 這個重複的數 。

你設計的解決方案必須不修改數組 nums 且只用常量級 O(1) 的額外空間。

---
以[1,3,4,2,2]為例, 可作關係圖如下:

可以看到因為nums[2]=4, nums[4]=2導致圖中出現環, 而環的入口即為重複值(nums[3]=nums[4]=2, 2重複)。

證明環存在的方法為使用雙指標, 一個一次移動一格, 另一個一次移動兩格, 當兩指標相遇時, 代表快的指標贏過慢指標一圈(或更多圈), 此時可證明環的存在。

若兩點在紅點處相遇, 此時slow走的距離為a+c, fast走的距離為a+2c+b, 而因為fast走的速度是slow的兩倍, 於是可得關係 2(a+c)=a+2c+b, a=b。因此, 將其中一點退回原點, 並將兩點以每次一格的距離移動, 最終他們將在環的入口再次相遇(也就是這題的重複數字)。

---

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