[leetcode]217. Contains Duplicate

題目：217. Contains Duplicate
關鍵字：集合(set)

集合(set)：只能用來判斷「有沒有」而不能判斷「有幾個」，也不能判斷加入先後的資料結構，可以很快速的加入資料以及判斷資料是否存在。

第一版，直覺的想法

「直接把允許內容重複的陣列轉成集合，如果集合的長度比陣列短就表示有重複的值」，聽起來蠻合理的對吧？

雖然通過了但資源使用的效率落在後頭，這點完全符合預期，畢竟我們只要確認是否有重複，全部去重複是不必要的工作。

第二版，符合實務想法的集合使用

依序確認陣列的所有數字，如果集合內發現已經存在就表示重複，集合裡沒有就加入集合，直到全數確認完畢都沒發現重複就表示不重複。

從執行時間的落點可以發現，這應該算是本題的主流解法，或者與主流解法效率相同，只要對集合有點了解就能想到，並不困難。

第三版，先加入再確認結果

記錄原本集合的長度，不做判斷地加入新的數字後再確認集合是否確實加入新元素(長度變長)，以此判斷這個數字是否重複。

由於原本使用的contains實際上也是在集合內比對是否有相同的元素，隨著集合元素數量增加比對花費的時間也會變長，省去這段搜索的功夫直接確認長度的變化會更快，效率的表現上也超越原本大多數解答的執行時間。

第四版，發掘函式沒想到的特性

set.add(num) 除了原本不存在就加入，存在就跳過之外，它的回傳值還可以用來分辨集合原本是否存在耶！

說實話，以前的我大概做到上一步就結案了，這次是想著「加入新元素時其實也會判斷原本有沒有吧？」心血來潮研究之後，注意到原始碼的說明。

在了解這個事實之前，第二版程式使用contains和add在檢查每個數字的時候都多做一次集合內的搜尋，也就不意外改進之後效率能再次提升了。

這是我能想到最精簡，也是最有效率的寫法了。

番外第一版，先排序再比較

呼叫排序功能排序後，再依序檢查所有數字是否與相鄰的元素相等。

速度比第一版的直接轉為集合略快，但記憶體用的更多，畢竟排序的過程多少也需要額外空間，最核心的還是這方法也多費了額外不必要的功夫。

有些時候解題不一定需要多特別的想法，只是多知道了一點知識就能讓結果出現差異。這次研究的成果雖然不大，不過以後只要是使用集合的場合都能精進，或許也算是一天進步1%的表現？