题目描述

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

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

样例

输入：[1,2,3,1]
输出：true

输入：[1,2,3,4]
输出：false

输入：[1,1,1,3,3,4,3,2,4,2]
输出：true

算法

(集合判重) $O(n)$

1. 使用 unordered_set，存放数组中的整数。
2. 从头开始扫描数组，发现当前扫描到的整数存在于集合中，则返回 true；否则加入到集合中。
3. 扫描完毕后返回 false。

时间复杂度

• unordered_set 的单次插入和查询时间复杂度为 $O(1)$，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储集合。

C++ 代码

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> v;

        for (int i = 0; i < nums.size(); i++) {
            if (v.find(nums[i]) != v.end())
                return true;

            v.insert(nums[i]);
        }

        return false;
    }
};