###### 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)

* **技巧**
* 將位置與數字關係結合:

        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**

       (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:

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++:

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;
    }
};