0217. Contains Duplicate (Easy)

(當然，Medium的拍手也可以多拍幾下啦XD)

Question

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1

1
2

Input: [1,2,3,1]
Output: true

Example 2

1
2

Input: [1,2,3,4]
Output: false

Example 3

1
2

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

分析/解題

給定一個整數陣列，若陣列有任何重複的數，則回傳true，否則回傳false。

今天來點簡單的，畢竟中秋節嘛XD
和之前找出單一元素的題目不同，因為這題沒有限定重複出現的次數 ，
所以並不適用於bitwise operation 的方法。

以暴力法來說要O(N²)，排序後再比要O(NlogN) ，
均不理想，所以一般常見的想法是，
一樣引入hashmap或dictionary 來解題。

而由於我們只在意數字有沒有出現 ，對於Java來說，
還有另外一個名為HashSet 的方式可以使用。
HashSet在新增 方面複雜度同於HashMap均為O(1) ，
但HashSet同時具備Set的特性，同個資料只能出現在Set當中一次 ，
若有相同資料要被新增時，則新增會失敗(回傳false) ；
我們可以利用這點，每次對HashSet新增當前的數字，
失敗則代表已經出現重複了(直接回傳true)，
若全數新增完畢則代表不存在重複(回傳false)。

Java

Python的set新增時碰到重複的資料時不會進行任何動作 ，
所以這邊還是使用dictionary。
另一種作法是可以使用set來進行化簡後，直接檢查總長度是否改變 ，
即可知道是不是含有重複的元素。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(N)，因為每次插入均為O(1))

「如果限制不用HashSet/Dictionary，但給你nums值的範圍呢？」
(建立一個array/list，總長為整個範圍，
將其拿來做為輔助陣列使用即可。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~