LeetCode 尋找重複數：鏈表環檢測映射法 O(n) 時間 O(1) 空間

題目約束

• 數組長度 n+1，元素範圍 [1, n]，至少一個重複。
• 只有一個重複數字（可重複多次）。
• 不可修改數組、O(1) 額外空間、時間 O(n²) 以下。

核心洞察：下標-值映射構成鏈表

將下標 i 映射到 nums[i]。無重複時形成排列（每個節點入度出度均為 1）；有重複時出現多對一映射，必然形成環。環入口即為重複數。

例：nums = [2, 1, 3, 1]
映射：0→2, 1→1, 2→3, 3→1 → 序列 0→2→3→1→1→... 環入口為 1。

Floyd 快慢指針三步法

1. 判斷有環：slow = nums[slow], fast = nums[nums[fast]]，相遇證明有環（即有重複）。
2. 找環入口：finder = 0，slow 留在相遇點。雙指針同速 slow = nums[slow], finder = nums[finder]，再次相遇點即入口 = 重複數。
3. （數學證明：頭節點到入口距離 = 相遇點到入口距離 + k×環長）

C++ 精簡實現

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        // 階段 1：相遇
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        // 階段 2：找入口
        int finder = 0;
        while (slow != finder) {
            slow = nums[slow];
            finder = nums[finder];
        }
        return slow;
    }
};

複雜度

• 時間 O(n)：快指針最多走 2n 步。
• 空間 O(1)：僅常數變量。

對比：二分法

值域二分 [1, n]，統計 ≤ mid 的元素個數，若 > mid 則重複在左半區。時間 O(n log n)，空間 O(1)，理解較直觀但非最優。