287. Find the Duplicate Number

Find the Duplicate Number

題目描述：給定一個包含 n + 1 個整數的陣列 nums，其中每個整數都在 [1, n] 範圍內。根據鴿巢原理，陣列中必定存在至少一個重複的數字。請找出並返回那個重複的數字。限制條件：不能修改原陣列，且只能使用 O(1) 額外空間。

解題思路：此題最優解是 Floyd's Cycle Detection（Floyd 判圈演算法，龜兔賽跑算法），將陣列視為一個隱式的鏈結串列來處理。

為何其他方法不完全符合要求？

• 排序：O(n log n) 時間且需要修改原陣列，不符合限制。
• XOR 或加法公式：只適用於「恰好一個數字重複一次」的情況；若重複數字出現超過兩次，計算結果不正確。
• 哈希表：雖然 O(n) 時間，但需要 O(n) 額外空間，不符合限制。

Floyd's Cycle Detection 的核心思想：

將每個索引 i 視為節點，將 nums[i] 視為從節點 i 指向節點 nums[i] 的邊，構成一個隱式的有向圖。由於有重複數字，必然存在兩個不同的索引指向同一個節點，從而形成環。

三個步驟：

1. 尋找相遇點：慢指標每次走一步（slow = nums[slow]），快指標每次走兩步（fast = nums[nums[fast]]），直到相遇。
2. 找環的入口：將慢指標移回起點 0，快指標留在相遇點，兩者每次各走一步，再次相遇的節點即為環的入口，也就是重複的數字。
3. 返回結果：返回再次相遇時的節點值。

時間複雜度：O(n) — Floyd 判圈演算法分兩個階段：第一階段找相遇點，第二階段找環的入口。兩個階段的走訪步數均與串列長度（即陣列長度 n）成線性關係，因此整體時間複雜度為 O(n)。

空間複雜度：O(1) — 整個演算法只使用了兩個指標變數（slow 和 fast），不需要哈希表、額外陣列或任何與輸入規模成比例的輔助空間，完全滿足題目的空間限制要求。

哈希表 O(n) 時間 / O(n) 空間：走訪陣列，將每個數字存入哈希集合，若發現數字已存在則直接返回。實作最簡單，但需要 O(n) 額外空間，不符合本題的空間限制，僅適合作為暴力解或快速驗證答案使用。

二分搜尋（按值域）O(n log n) 時間 / O(1) 空間：對值域 [1, n] 進行二分搜尋。對於中間值 mid，統計陣列中小於等於 mid 的數字個數 count。若 count > mid，代表重複數字在 [1, mid] 範圍內；否則在 [mid+1, n] 範圍內。此方法滿足空間限制，但時間複雜度為 O(n log n)，不如 Floyd 演算法的 O(n) 優秀，且僅在重複數字只出現兩次時保證正確。

排序後線性掃描 O(n log n) 時間：先對陣列排序，再線性掃描找到相鄰相等的數字。此方法違反「不得修改原陣列」的限制，不符合題意。

1. 若陣列中可能有多個不同的重複數字（例如 [1, 2, 2, 3, 3]），Floyd 演算法還能找出所有重複數字嗎？若不能，你會改用什麼方法？
2. 為什麼題目要求不能修改原陣列，且只能用 O(1) 空間？如果去掉這兩個限制，你最傾向於使用哪種解法，理由是什麼？
3. Floyd 判圈演算法也常用於偵測鏈結串列中的環（LeetCode 142）。請說明本題的「陣列映射 i → nums[i]」與鏈結串列場景之間的對應關係是什麼？