Leetcode skimming ---217

subject ： Given an array of integers  nums . If any value appears in the array   At least twice  , return  true ; If each element in the array is different from each other , return  false .

Input ：nums = [1,2,3,1]

Output ：true

Method 1 ： Sort

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

Complexity analysis

Time complexity ：O(NlogN)

Spatial complexity ：O(logN)

Method 2 ： Hashtable

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

Complexity analysis

Time complexity ：O(N)

Spatial complexity ：O(N)