LeetCode 217. 存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

输入:

[1,2,3,1]

输出:

true

示例 2:

输入:

[1,2,3,4]

输出:

false

示例 3:

输入:

[1,1,1,3,3,4,3,2,4,2]

输出:

true

代码：

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

提交结果：

思路：

由于输入的数组并无法确定是否有序，同时条件中并未要求数组保持原样，所以为避免双循环，可以先将
数组进行排序，因此判断数组中是否存在重复元素，仅需要判断判断数组中一个元素前后是否有相同元素。
同时如果需要保持数组保持不变，则可以将代码转入函数中实现。

复杂度分析：

• 时间复杂度：O(NlogN)，其中N为数组的长度。需要对数组进行排序。

• 空间复杂度：O(logN)，其中N为数组的长度。注意我们在这里应当考虑递归调用栈的深度。

官方答案：

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

提交结果：

思路：

对于数组中每个元素，我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，
则说明存在重复的元素。

复杂度分析：

• 时间复杂度：O(N)，其中N为数组的长度。
• 空间复杂度：O(N)，其中N为数组的长度。