287 Find the Duplicate Number
看到一個很聰明的解法，可是不通為什麼這樣可以work，所以想釐清思路。
跨一步跟兩步
首先回答一個問題，為何一次走一步跟一次走兩步的方法是
slow = nums[slow];
fast = nums[nums[fast]];
原因是，解法要用Linked List Cycle II的演算法，所以要先從given array造出一個cycled linked list。
定義一個新的 iterate 行為
首先讓我們來看一個沒有duplicate element的array:
array: 2 3 1
index: 0 1 2
先定義一個函數是f(index)=element。可知:
array: 1 2 0
index: 0 1 2
f(0) = 1
f(1) = 2
f(2) = 0
現在，我們定義一種新的iterate行為，可以從0開始走過所有element:
f(0) = 1
f(f(0)) = f(1) = 2
f(f(1)) = f(2) = 0
每一次操作，取前一次的結果來當作新的f()的輸入，就定義為走一步。
利用新的 iterate 行為來走duplicate array
現在讓我們考慮有duplicate element的array:
array: 2 3 1 4 3
index: 0 1 2 3 4
由於有duplicate element，勢必有兩個以上的index對應到value相同的element!
這時上面定義的新iterative行為才發揮價值，因為從0開始，就可以看到從3為起點，形成cycle:
f(0) = 2
f(f(0)) = f(2) = 1
f(f(2)) = f(1) = 3
f(f(1)) = f(3) = 4
f(f(3)) = f(4) = 3
f(f(4)) = f(3) = 4
現在既然我們已經可以利用新的iterative操作，造出一個有cycle的linked list，問題其實已經被簡化成Linked List Cycle II。接下來看下一個問題。
Reference
感恩Sherry實際舉了個例子，再配合這個blog點出f(index)這個操作，才讓我懂跨一步跟跨兩步的真正意義。
為何最後相遇的地方就是環的起點?
下一個問題是，為何最後相遇的地方就是環的起點?
演算法步驟
演算法分成兩個步驟
- slow 跟 fast 分別走，第一次會在 x 相遇
- 將 fast 設為 0 (回到下圖中的S)，跟slow一起走 a 步，就可以在 cycle 起點 O 相遇
為何可以確定在 O 相遇 - 觀點1
先想像我們今天只有一個 circular linked list，走 c 步可以走完一圈。假設我的 slow 跟 fast 從同一點 x 開始走，slow 走 c 步後會回到 x (剛好走一圈)，這時 fast 已走了 2c 步(剛好走兩圈)，也會回到同一點 x。
所以當他們同時從 linked list 起點 S 出發 (在O 前面 a 步處)，他們一定也會在 cycle 中的 O 前面 a 步處相遇。
為何可以確定在 O 相遇 - 觀點2
先給下列定義:
從cycle起點O走到x:p步
從S走到O:a步
從O走一圈cycle:c步
首先，假設 slow 在 x 點被 fast 追上時，它走了 s 步，那 fast 就走了 2s 步。既然 slow 跟 fast 都抵達 x，表示 s 跟 2s 差了 n 圈(只是n是多少我們不知道)，可以寫出(1)式:
2s = s + n*c
=> s = n*c ...(1)
我們還已知相遇時，slow 走了 a+p 的距離，所以可以寫出(2)式:
s = a+p ...(2)
綜合(1)跟(2):
s = n*c ...(1)
s = a+p ...(2)
=> a+p = s = n*c
=> a+p = n*c
=> a+p = (n-1)*c+c
=> a = (n-1)*c+(c-p)
c-p 就表示 x 到 O 的距離。所以，如果讓 fast 回到 S，當 fast 走 a 步之後，slow 就走了 (n-1)c+(c-p)，走 (n-1)c 步不重要，因為還是回到 x，重點是補走了 c-p 步 ，才能在 O 相遇。