217. Contains Duplicate

題目網址：https://leetcode.cn/problems/contains-duplicate/

題意：給一整數 array nums, 判斷當中是否有重複數字。

Solution 1：

想法：先排序, 再用 loop 兩兩比較 nums[i - 1] 和 nums[i] 是否相等

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

• time：$O(n\cdot log(n))$ ➔ sorting
• space：$O(1)$ ➔ sorting 後 data 仍儲存在 nums 中, 不需要額外空間

Solution 2：

想法：利用 hash table 紀錄出現過的元素

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for (const auto& num : nums) {
            if (s.find(num) != s.end()) {
                return true;
            }
            s.emplace(num);
        }
        return false;
    }
};

• time：$O(n)$ ➔ for loop
• space：$O(n)$ ➔ s 長度不超過 n

Solution 3：

想法：比較 nums 和 set(nums) 長度是否相等, 若不相等代表有重複

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        return nums.size() != set(nums.begin(), nums.end()).size();
    }
};

• time：$O(n)$ ➔ 將 nums 轉成 set(nums)
• space：$O(n)$ ➔ set(nums) 長度不超過 n