# 217. Contains Duplicate

### Leetcode

<https://leetcode.com/problems/contains-duplicate/description/>

### 題目

Given an integer array `nums`, return `true` if any value appears **at least twice** in the array, and return `false` if every element is distinct.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [1,2,3,1]
</strong><strong>Output: true
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [1,2,3,4]
</strong><strong>Output: false
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [1,1,1,3,3,4,3,2,4,2]
</strong><strong>Output: true
</strong></code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一 - HashTable**

Time complexity: O(n)

Space complexity: O(n)

```javascript
var containsDuplicate = function(nums) {
    const map = new Map();

    for(let i=0; i<nums.length; i++) {
        const value = nums[i];
        if (map.has(value)) {
            return true;
        }
        map.set(value, i);
    }

    return false;
};
```

Runtime: 91 ms Beats 33.46% of users with JavaScript

Memory: 66.92 MB Beats 5.39% of users with JavaScript

* **方法二 - Sorting**

Time complexity: O(nlogn)

Space complexity: O(1)

```javascript
var containsDuplicate = function(nums) {
    nums.sort((a, b) => a - b);

    for(let i=0; i<nums.length; i++) {
        if (nums[i] === nums[i+1]) {
            return true;
        }
    }

    return false;
};
```

Runtime: 140 ms Beats 17.79% of users with JavaScript

Memory: 59.30 MB Beats 46.14% of users with JavaScript

* **方法三 - Set**

直接使用原生的 Set 方法

```javascript
var containsDuplicate = function (nums) {
    const s = new Set(nums)
    return s.size !== nums.length
};
```

### 參考資料 <a href="#ti-jie" id="ti-jie"></a>

{% embed url="<https://medium.com/roywannago-%E6%97%85%E8%A1%8C%E4%B8%8D%E9%9C%80%E7%90%86%E7%94%B1/leetcode-%E5%88%B7%E9%A1%8C%E7%B4%80%E9%8C%84-217-contains-duplicate-easy-647bc2ccdcf6>" %}

{% embed url="<https://zxi.mytechroad.com/blog/hashtable/leetcode-217-contains-duplicate/>" %}
