217. Contains Duplicate

Link bài toán trên Leetcode: https://leetcode.com/problems/contains-duplicate/description/

[EASY] 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, 5, 5]

Output: True

Explanation: The element 5 occurs at the indices 3 and 4.

---

Example 2:

Input: nums [1, 2, 3, 6, 8,]

Output: False

Explanation: All elements are distinct.

1. Brute Force

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

• Time complexity: O(n²)

• Space complexity: O(1)

---

2. Sorting

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 complexity: O(n log n)

• Space complexity: O(1) or O(n)

---

3. Hash Set

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set <int> seen;
        for (int num : nums) {
            if (seen.count(num)) {
                return true;
            }
            seen.insert(num);
        }
        return false;
    }
};

• Time complexity: O(n)

• Space complexity: O(n)

---

4. Hash Set Length

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

• Time complexity: O(n)

• Space complexity: O(n)