217. Contains Duplicate

https://leetcode.com/problems/contains-duplicate/

Problem

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:

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

Example 2:

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

Example 3:

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

Solution

1. Hash Map (Concise)

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

2. Hash Map (Optimized)

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if (nums.size() < 2) return false;
        const int min = *min_element(nums.begin(), nums.end());
        const int range = *max_element(nums.begin(), nums.end()) - min  + 1;
        int counter[range];
        for (int i = 0; i < range; ++i) counter[i] = 0;
        for (const auto &n: nums) counter[n - min]++;
        for (const auto &n: nums) if (counter[n - min] > 1) return true;
        return false;
    }
};

3. 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 - 1] == nums[i]) return true;
        }
        return false;
    }
};

• #hash

• #sorting