# 287. Find the Duplicate Number (1)

[Link](https://leetcode.com/problems/find-the-duplicate-number/)

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

**Example 1:**

```
Input: [1,3,4,2,2]
Output: 2
```

**Example 2:**

```
Input: [3,1,3,4,2]
Output: 3
```

**Note:**

1. You **must not** modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than *O*(*n*2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

**Solution**

這個問題之前在Movial面試被問過，當初用realsum -  sum(1\~n) 的方法帶過，但實際上不能用。因為數字可能重複多次。(ex. 2,2,2,2,2)

第一個想法是用set 去做，但space complexity would be O(n)

**方法二: (cycleing link)**

因為nums裡的value會介於len-1\~0之間, len為nums大小，所以可以用這個方法。

用兩個指標，根據nums裡的value值決定下一個點的位置，然後slow的一次改變一次位置, ie. slow = nums\[slow];

fast一次會改變兩次ie. fast = nums\[nums\[fast]]

當slow = fast時，代表兩種不同速度的指標會合在同一個位置。表示有一個cycling出現。

接下來就是找到cycling的入口，也就是重複的點，根據以下推論:

m = xn -k; 所以當slow留在原地，fast重頭開始一起慢慢走，最後會合的就會是loop entry。

![](https://2628390332-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M0RnkuvOeqe0clAIN1b%2F-M2g7ovelZr_gJQxHb5U%2F-M2gP84raDnq7Q97c44i%2Fimage.png?alt=media\&token=06ad98ef-bb49-4208-9e0e-83bae7ff3a3f)

讓slow維持在原位置，fast回到起點(index=0)，slow與fast一起一步一步地走 看何時走到一起。那時就是起點。

**目前只能先硬記結果了，應該很難現場想到**

```
  public int findDuplicate(int[] nums) {
        int fast = 0, slow = 0;
        do{
            fast = nums[nums[fast]];
            slow = nums[slow];
        }while(fast != slow);
        
        fast = 0;
        while(fast != slow){
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
```
