# Find the Duplicate Number 287

###### tags: `leetcode`,`two pointer`,`medium`

>ref: 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.

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

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

>Constraints:
1 <= n <= 10^5
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.

>1. spatialCom(O(N)) time(O(N))
>2. method like dictionary

class Solution {
    public int findDuplicate(int[] nums) {
        
        boolean[] visited= new boolean[nums.length];
        
        int i=0;
        
        while(i>=0 && !visited[i]){
            visited[i]=true;
            i=nums[i];
        }
        return i;
    }
}

>1. use fast slow two point, owing the duplicate as a close circle.
>2. fast/slow diff is fast point faster than slower point one step. when the two meet(must in the close circle), place one point at the starter, make them run as same speed, then they meet in the duplicate point.


[ref](https://leetcode.com/problems/find-the-duplicate-number/discuss/72846/My-easy-understood-solution-with-O(n)-time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation.)

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