在 LeetCode 217 題「Contains Duplicate」中，我們需要檢查一個整數陣列中是否包含重複的元素。如果陣列中有重複的數字，則回傳 true；否則回傳 false。

題目：
給定一個整數陣列，我們需要確定陣列中是否有任何元素出現超過一次。如果有任何重複的元素回傳 true，否則回傳 false。

範例：

輸入: [1,2,3,1]
輸出: true
解釋: 數字 1 出現了兩次，因此回傳 true。

解題思路

這題的重點在於如何快速檢查是否有重複的數字。由於我們要找出是否存在重複值，因此使用適當的資料結構來追蹤我們遍歷過的數字是解決這題的關鍵。這裡有兩種做法。

解法 1：使用 Hash Set

unordered_set可以幫助我們快速檢查和插入元素，並且查找元素的時間複雜度是 O(1)。步驟如下：

1. 我們遍歷每個數字，並檢查它是否已經存在於set中。
2. 如果數字已經存在set中，則表示找到重複值，立即回傳 true。
3. 如果數字不在set中，則將其加入set繼續遍歷。
4. 最後遍歷結束後，如果沒有找到任何重複值，則回傳 false。

判斷重複的寫法 set.find(nums[i]) != set.end() 跟 set.count(num) 都可以

這種方法的時間複雜度為 O(n)，因為我們需要遍歷整個陣列一次，並且每次插入和查找的時間複雜度都是 O(1)。

實作：

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> set;
        for (int i = 0; i < nums.size(); i++) {
            if (set.find(nums[i]) != set.end()) { // 有重複
            //if (set.count(num)) { // 有重複
                return true;
            }
            set.insert(nums[i]);
        }
        return false;
    }
};

解法 2：先排序再遍歷

另一個方法是先對陣列進行排序，然後檢查相鄰的元素是否相等。如果有相等的相鄰元素，則代表重複，就回傳 true。如果遍歷結束後沒有找到重複，則回傳 false。

這種方法的時間複雜度為 O(n log n)，因為排序的時間複雜度是 O(n log n)，而遍歷一次的時間複雜度是 O(n)。

實作：

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size()-1; i++) {
            if (nums[i] == nums[i+1]) { // 有重複
                return true;
            }
        }
        return false;
    }
};

參考：
#217. Contains Duplicate