---
# System prepended metadata

title: 287. Find the Duplicate Number
tags: [pointer, Leetcode, medium, python, c++, Top 100 Liked Questions]

---

###### tags: `Leetcode` `medium` `pointer` `python` `c++` `Top 100 Liked Questions`

# 287. Find the Duplicate Number

## [題目連結:]https://leetcode.com/problems/find-the-duplicate-number/

## 題目:
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.

**Follow up:**

* How can we prove that at least one duplicate number must exist in nums?
* Can you solve the problem in linear runtime complexity?

**Example 1:**
```
Input: nums = [1,3,4,2,2]
Output: 2
```
**Example 2:**
```
Input: nums = [3,1,3,4,2]
Output: 3
```

## 解題想法:
* 給一數組，共有n+1個數字，由1~n組成，
    * 只有一數出現兩次，找出該數
    * time: O(n)
    * space: O(1)

* **技巧**
    * 將位置與數字關係結合:
    ``` python=
        pos= 0 1 2 3 4
      nums= [1,3,4,2,2]
    抽象想!! pos->nums->pos->nums......
    為0->1  1->3  2->4  3->2  4->2 
    * 即nums[i]存的是下個要指的位置
    * 所以可化為: 0->1->3->2->4->2->4.......loop
    ```

* 使用pointer:
    * **可想成找環的問題** => **重複值=環的入口**
    * 證明:
    * 設 **環的長度為(B+C)** 進入環之前的路為**A**
    ``` python=
       (A) (重複點) (B)  (x)
    ---------->---------->
              |          |
               -----------
                    C
    ```
    * 設slow與fast相遇點為x
        * 則slow共走了A+B
        * fast走了A+2B+C
    * 因為fast=2 * slow
    * 所以A+2B+C=2A+2B
    * 所以**A=C**
    * 可以得證: 
        * 對於原點而言，走A的距離，相當於**同時從相遇點x走A的距離** 彼此相交的位置，即為重複值


## Python:
``` python=
class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        slow=nums[0]
        fast=nums[nums[0]]
        while fast!=slow:
            slow=nums[slow]
            fast=nums[nums[fast]]
        start=0 #起始
        while start!=fast: #此處fast已經為fast slow相交處
            #各自一步步移動
            start=nums[start]
            fast=nums[fast]
        return start

result=Solution()
ans = result.findDuplicate(nums = [1,3,4,2,2])
print(ans)
```

## C++:
``` cpp=
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow=nums[0],fast=nums[nums[0]];
        while (slow!=fast){
            slow=nums[slow];
            fast=nums[nums[fast]];
        }
        int start=0;
        while (start!=fast){
            start=nums[start];
            fast=nums[fast];
        }
        return start;
    }
};
```