---
# System prepended metadata

title: Leetcode 217. Contains Duplicate
tags: [Array]

---

###### tags: `Array`
<h1>Leetcode 217. Contains Duplicate</h1>
<ol>
    <li>問題描述</li>
    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.<br><br>
    
Example 1:
    
    Input: nums = [1,2,3,1]
    Output: true
    
Example 2:
    
    Input: nums = [1,2,3,4]
    Output: false
    
Example 3:
    
    Input: nums = [1,1,1,3,3,4,3,2,4,2]
    Output: true
    
<li>Input的限制</li>
    <ul>
        <li>1 <= nums.length <= 10^5</li>
        <li>-10^9 <= nums[i] <= 10^9</li>
    </ul>
    <br>

<li>思考流程</li>
    <ul>
        <li>Set</li>
        當我們要檢查一個 array 裡面有沒有重複的元素，一個簡單的方法就是把看過的元素記下來，當整個 array 掃過一遍後，我們就能確認裡面有沒有重複的元素。使用 set() 來紀錄數字，當發現 set 裡面已經有相同的數字，就 return True，整個 array 掃描完都沒發現有重複的數字，return False。
        <br>
        <br>
        因為需要走過 array 一遍，所以 time complexity 是 O(n)；最差的情況下，set 內會放滿接近整個 array 的數字，故 space complexity 是 O(n)。
        <br>
        <br>
        Time Complexity: O(n); Space Complexity: O(n)
        <br>
        <br>
        <li>元素的數目</li>
        另一種做法是利用 python set() 的特性，因為其內不允許有重複的元素，所以我們直接把整個 array 加入到 set 中，並看整個 set 與 array 的大小是否相等。若不相等則代表有重複元素，相等代表所有元素皆相異。
        <br>
        <br>
        把整個 array 加入到 set 內需要加入 n 個元素，所以 time complexity 是 O(n)、space complexity 是 O(n)。
        <br>
        <br>
        Time Complexity: O(n); Space Complexity: O(n)
        <br>
        <br>
    </ul>
<li>測試</li>
    <ul>
        <li>test 1( edge case )</li>
        如果 input 為 empty array，則須回報錯誤訊息。
        <li>test 2( edge case )</li>
        如果 list 內有元素不是數字，也須回報錯誤訊息。
        <li>test 3</li>
        Input: prices = [1, 2, 5, 8, 10]<br>
        Output: False
        <li>test 4</li>
        Input: prices = [2, 2, 4, 2]<br>
        Output: True
</ol>