数据结构每日一题1

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false。

1.暴力解

这是我一开始最先想到的

class Solution {

public:

bool containsDuplicate(vector& nums) {

int i =0;

for (i;i<(nums.size()-1);i++)

{

for (int j =i+1;j

{

if (nums[i] == nums[j]){

return true;}}}

return false;}};

很显然会超出时间

2.先对数组排序，再比较相邻的元素，会减少时间复杂度

class Solution {
public:
    bool containsDuplicate(vector& 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;
    }
};

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

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