# 287-Find the Duplicate Number
###### tags: `Medium`
## Question
https://leetcode.com/problems/find-the-duplicate-number/
## Key
1. Hash table
complexity比較高
2. 2 pointers 快慢指针
速度快且用較少空間
## Reference
https://www.cnblogs.com/grandyang/p/4843654.html
## Solution
### 2 pointer solution

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if (nums.size() > 1)
	{
		int slow = nums[0];
		int fast = nums[nums[0]];
		while (slow != fast)
		{
			slow = nums[slow];
			fast = nums[nums[fast]];
		}

		fast = 0;
		while (fast != slow)
		{
			fast = nums[fast];
			slow = nums[slow];
		}
		return slow;
	}
	return -1;
    }
};

### Hash table solution

public:
    int findDuplicate(vector<int>& nums) {
        unordered_map<int,int> umap;
        int n = nums.size();
        for(int i=0; i<n;i++)
        {
            umap[nums[i]]++;
        }
        for(int i=0; i<n;i++)
        {
            if(umap[nums[i]]>=2)
            {
                return nums[i];
            }
        }
        return -1;
    }
};