217 Contains Duplicate

题目

217 Contains Duplicate

题解

题目要求：检验数组是否有重复的元素。

这里提出两种解法

1. 暴力求解：对每个元素i，遍历在其之后的所有元素，检查有没有跟元素i相同的元素。时间复杂度为\(O(n^2)\)，空间复杂度为\(O(1)\)
2. 利用数据结构哈希表：哈希表以元素值为key，出现的次数为value。在遍历元素的同时在哈希表中更新value，即元素出现的次数。若遍历过程中发现value大于一的元素，则该数组含有重复元素。时间复杂度为\(O(n)\)，空间复杂度为\(O(n)\)。这是一种以空间换时间的做法。

代码

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