287. 尋找重復數

給定一個包含?n + 1?個整數的數組?nums?，其數字都在?[1, n]?范圍內（包括?1?和?n），可知至少存在一個重復的整數。

假設?nums?只有?一個重復的整數?，返回?這個重復的數?。

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

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

最優方法，將數組視為鏈表，重復值意味著有多個節點指向同一位置，即有環，問題轉換為找環，之前刷過，具體思路如下。

1. 將數組視為鏈表??：將數組中的值視為指向下一個索引的指針。例如，nums[i]表示?i -> nums[i]。因為有重復的數字，所以至少有兩個不同的索引會指向同一個位置，形成環。

2. ??檢測環的入口??：使用快慢指針，快指針每次走兩步，慢指針每次走一步，直到兩者相遇。然后讓一個指針從起點開始，另一個從相遇點開始，每次各走一步，再次相遇的點就是環的入口，即重復的數字