Leetcode 217. Contains Duplicate

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