前言

今天先暫停一下sum的題目，來做top 100 liked的另外一題─287. Find the Duplicate Number。

想法

這題其實光是官方解答就非常精彩~ 提供了7種解法。其實這題如果沒有特別限制的話，非常簡單。不過題目同時設下了三個限制就讓可行的方式少了很多：

1. constant space=> 空間複雜度 O(1)
2. without modifying the array nums
3. linear time=> 時間複雜度 O(n)
   雖然第三個是額外挑戰啦~ 沒有寫在題目正文中。
   如果沒有這些限制的話，可以用一個set來記錄看過的，遇到有看過的就回傳，遍歷一次就可完成，但空間複雜度會是O(n)；或者經過sort排列，這樣一樣的數字就會排在隔壁，然後再遍歷一次看前後有沒有相同的，但這樣會更改到原本的array，且時間複雜度為O(nlogn)；或者是利用題目說出現的數字會在1~n之間的特性，把出現數字做為index，去把那位數更改成負的，這樣下次遇到發現有負數的話就代表該數字被改過了，不過這也違反不能modify原本array的限制。
   最後官方提供的解答中，最後只有一種方式符合題目的三項規定：

Floyd's Tortoise and Hare (Cycle Detection)

我們直接來看解答，再來分析這個解法的想法：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {

        // Find the intersection point of the two runners.
        int tortoise = nums[0];
        int hare = nums[0];

        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);

        // Find the "entrance" to the cycle.
        tortoise = nums[0];
        while (tortoise != hare) {
            tortoise = nums[tortoise];
            hare = nums[hare];
        }

        return hare;
    }
};

它是利用cycle detection的概念，其實跟142. Linked List Cycle II這題的概念有關。這個解答的變數命名有點生動XD
簡單來說，它把這題當成有點linked list的概念，因為它限制nums[i]的值都會在1~nums.size()-1之間，那就必定可以找到一個nums[nums[i]]的值，我們就把它當成是一個next指標，指到它存在的地方的值。那我們接下來就用"快慢指針法"(解法叫龜兔賽跑法)，總之，就讓快的那個走的速度是慢的兩倍快，至於它怎麼走？就是按照linked list next的位置去走。那如果有重複的數字出現，代表會有兩個(或更多)的數字會走到同一個點，然後就會重複該點的動作，進入一個迴圈。
進入迴圈代表什麼呢？代表快指針會碰得到慢指針。而當它碰到的時候，我們就可以來計算迴圈的起始點=重複點了。
此時就讓一個從起點重新出發，一個從目前的碰頭點出發，再次碰到的時候就是迴圈起始點了。
如果還有疑問的話，也可以到官方解答去看圖片詳解。
不如明天就來詳解142. Linked List Cycle II這題概念吧！

結語

話說，這題限制那麼多，根本是hard。solution 1~7已經各種技巧都出來了，可以再去官方解那邊慢慢看~
接戲來再回歸sum系列題目挑戰~