# 217. Contains Duplicate

[leetcode網址](https://leetcode.com/problems/contains-duplicate/description/)

## 問題
在一個陣列中找出兩個重複的數字，有就回傳true，沒有就回傳false

Input: nums = [1,2,3,1]

Output: true
        The element 1 occurs at the indices 0 and 3.

## Time=O(N)||Space=O(N)
### Idea
寫完[two sum](https://hackmd.io/@clh/leetcode-record/https%3A%2F%2Fhackmd.io%2F%40clh%2Fleetcode-1)
這題應該就知道 `unordered_map` 有多好用了，所以這題要用的是類似的hash set(`unordered_set`)，但我只要一個位置存一個element，為了好搜尋所以用了hash set
1. 跌代整個陣列
2. 檢查這個數字是否已經存在hash set中
- 有的話就回傳true
- 沒有的話就把數字存到set中

### Solution

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int>set;
    for(auto&num: nums){
        if(set.count(num))return true;
        set.insert(num);
    }       
    return false;
}

## Time=O(NlogN)||Space=O(1)
### Idea
1. 直接把`nums`先進行排序
2. 如果相鄰的數字相同就回傳觸，否則false

### Solution
:bulb: `ranges::sort` 會造成O(nlogn)的時間複雜度

bool containsDuplicate(vector<int>& nums) {
    ranges::sort(nums);
    for(int i=1; i<nums.size(); i++){
        if(num[i] == num[i-1])return true;   
    }
    return false;
}