前言

今天要解的題目是 Find the Duplicate Number（尋找重複數字）。這道題有一點點小挑戰，因為我們需要在不修改原陣列的情況下，找出唯一重複的數字，並且只能使用常數級別的額外空間。聽起來像是一個謎題，不過別擔心，我們可以借助一些巧妙的技巧來解決它！讓我們一起來看看吧！

英文題目 Find the Duplicate Number

難度：Medium

題目描述：

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

給定一個包含 n + 1 個整數的陣列 nums，每個整數都在 [1, n] 之間，其中只有一個數字重複出現多次。請找出這個重複的數字。

你必須在不修改陣列的情況下解決這個問題，並且只能使用常數級別的額外空間。

範例 1：

輸入： nums = [1,3,4,2,2]

輸出： 2

範例 2：

輸入： nums = [3,1,3,4,2]

輸出： 3

範例 3：

輸入： nums = [3,3,3,3,3]

輸出： 3

思路

這題要求我們在不修改陣列且只使用常數空間的情況下找到唯一的重複數字，這意味著我們不能排序，也不能用哈希表來記錄已經出現的數字。
那麼，這樣的條件下，我們可以使用一個巧妙的雙指針技巧：快慢指針（Floyd's Tortoise and Hare Algorithm）。

這個算法通常用於檢測鏈結串列中的循環，而這道題中我們可以將陣列視作一個隱式的鏈結串列，然後利用快慢指針來檢測循環，從而找到重複的數字。

詳細步驟

1. 使用快慢指針來尋找循環：

   • 我們可以將每個數字視為鏈結串列中的一個節點，數字的值指向下一個節點的索引。這樣，我們的目標就是找到這個「鏈結串列」中的循環。
   • 我們使用兩個指針：
     • slow 指針每次移動一步。
     • fast 指針每次移動兩步。
   • 當 slow 和 fast 相遇時，說明有循環存在。

2. 找到循環的入口，也就是重複數字：

   • 接著，我們將 slow 指針重新移回起點，fast 指針保持在相遇的位置。
   • 然後，slow 和 fast 每次都只移動一步，當它們再次相遇時，相遇的節點就是循環的入口，也就是那個重複的數字。

3. 為什麼這樣有效？：

   • 這種方法利用了數字之間的映射關係，將問題轉化為檢測鏈結串列中的循環。
   • 這樣的算法可以在 O(n) 的時間內完成，並且只使用 O(1) 的空間。

實作

function findDuplicate(nums: number[]): number {
    let slow = nums[0];
    let fast = nums[0];

    // 找到循環的相遇點
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);

    // 找到循環的入口
    slow = nums[0];
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast];
    }

    return slow;
}

解題心法

1. 快慢指針法的妙用：

   • 雖然這題看似與鏈結串列無關，但我們可以將數字之間的映射視作隱式的鏈結串列，利用快慢指針來尋找循環的入口。

2. 為什麼會有循環？

   • 由於陣列中的數字範圍是 [1, n] 且數量是 n+1，這就意味著必然存在一個重複的數字。這個重複的數字會在鏈結串列中形成一個循環。

3. 相遇點與循環入口：

   • 當快慢指針相遇時，說明我們找到了循環。之後，將一個指針重新放回起點，兩個指針每次移動一步，再次相遇時的位置就是循環開始的地方，也就是我們要找的重複數字。

為什麼這樣處理？

這種方法巧妙地將陣列轉化為隱式的鏈結串列問題，並利用快慢指針找出循環。
這樣我們就可以在 O(n) 的時間內找到重複的數字，並且只使用 O(1) 的空間，非常符合題目對於空間複雜度的限制。

本次要點：

• 快慢指針：用來檢測循環，找到重複數字。
• 隱式鏈結串列：將陣列視作隱式的鏈結串列，每個數字的值指向下一個節點。
• O(n) 時間複雜度，O(1) 空間複雜度：有效且符合題目要求的解法。

這道題是不是讓人感覺到數學和資料結構的巧妙結合呢？這樣的解法在面試中非常常見，希望你能透過這個解法掌握快慢指針的使用！
期待下次我們一起挑戰更多有趣的題目吧！🚴‍♂️🚴‍♀️