217. Contains Duplicate 存在重复元素

题目链接
tag:

• Easy；

question：
  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

解法一：
  这道题比较简单，使用一个Hash-Table，遍历整个数组，如果哈希表里存在，返回true，如果不存在，则将其放入哈希表中，O(n)复杂度，代码如下：

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // Hash
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            if (m.find(nums[i]) != m.end()) return true;
            ++m[nums[i]];
        }
        return false;
    }
};

解法二：
  先将数组排个序，然后再比较相邻两个数字是否相等，时间复杂度取决于排序方法，本解法sort()，底层快排，时间复杂度O(nlog(n))，代码如下：

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;
    }
};