題目：
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 uses only constant extra space.
JavaScript
var findDuplicate = function(nums) {
};Example 1:
Input: nums = [1,3,4,2,2]
Output: 2Example 2:
Input: nums = [3,1,3,4,2]
Output: 3觀念：
- 因為要維持 space = BIgO(1) 所以不能用 hashmap
- 因為不能修改 原本的陣列，所以不能用 sort (也不能建立一個新的因為 space BigO(1) )
- 因為重複的數字可能不只一個，所以不能把總數加起來在來比對差，例如 [1,1,1,1,1,1]
- 我們可以利用的是：數字一定是在 n (陣列長度) 裡面，代表不會超過 n — 1
- 我們還可以利用：只有一個數字是重複的
- 可以用 Linked List 的概念來想，然後每一個數字代表的是 index pointer，例如
[1,3,4,2,2]代表的是 1 → 3 → 2 → 4 → loop to 2 again。當一個數字有兩個指標指向它，它就是一個循環的起點。 - 需要使用 Floyd判圈算法，也就是龜兔賽跑算法
Floyd 判圈算法：
要找到循環的起點有兩個步驟：
- 找到slow 跟 fast 相遇的點 (meeting point: m)
- 在開頭建立一個新的 slow2，slow 從 m 繼續每次走一步，slow2 從開頭走，找到兩者相遇的點，這就是循環的開頭 (beginning point : b)，這也就是我們要找的重複的數字。
(詳細解釋可以看最下方參考連結的影片）
Javascript 解題：
var findDuplicate = function (nums) {
// 1. find the meeting point of slow and fast
let slow = 0
let fast = 0
while (true) {
slow = nums[slow]
fast = nums[nums[fast]] // move twice
if (slow === fast) {
break // currently slow is at the meeting point
}
}
// 2. find the point where the second slow meet with the slow
let slow2 = 0 // start a new slow a index 0
while (true) {
slow = nums[slow]
slow2 = nums[slow2]
if (slow === slow2) {
return slow // that is the beginning of the cycle.
}
}
}解題步驟：
- 第一步：找到 meeting point
- 建立兩個指標，fast 跟 slow，fast 一次移動一格，slow 兩格
- 使用 while loop，兩個指標開始跑，直到跑到一個相遇的點上，結束 loop
- 第二部：找到循環起始點(重複數字)
- 建立一個新指標，slow2，起始點在開頭
- 使用 while loop，slow 跟 slow2 開始跑，直到跑到一個相遇的點上，結束 loop
- 回傳 slow (重複的數字)
