題目
給定一個包含?n + 1?個整數的數組?nums?，其數字都在?[1, n]?范圍內（包括?1?和?n），可知至少存在一個重復的整數。
假設?nums?只有?一個重復的整數?，返回?這個重復的數?。
你設計的解決方案必須?不修改?數組?nums?且只用常量級?O(1)?的額外空間。
示例
示例 1：
輸入：nums = [1,3,4,2,2] 輸出：2示例 2：
輸入：nums = [3,1,3,4,2] 輸出：3示例 3 :
輸入：nums = [3,3,3,3,3] 輸出：3
分析
我們可以把數組?nums?看作是一個特殊的鏈表。對于數組中的每個索引?i，將?nums[i]?視為從索引?i?指向的下一個節點的位置。由于數組中存在重復的數字，這就意味著在這個特殊的鏈表中會形成一個環，而重復的數字就是環的入口節點。
快慢指針法
核心思路是將數組看作一個鏈表，通過快慢指針來檢測鏈表中是否存在環，進而找到重復的數字。
時間復雜度：O()，?
?是數組的長度
空間復雜度：O(1)
class Solution {
public:int findDuplicate(std::vector<int>& nums) {// 初始化快慢指針int slow = nums[0];int fast = nums[nums[0]];// 快慢指針相遇，檢測環的存在while (slow != fast) {slow = nums[slow];fast = nums[nums[fast]];}// 慢指針回到起點slow = 0;// 快慢指針以相同速度前進，再次相遇的位置即為重復數字while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;}
}; 
)
