LeetCode Daily Question 4

Mar 8th 2022

3 月 8 日 每日一题

题目：217. Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

1
2
eg: Input: nums = [1,2,3,1]
Output: true

思路

首先对 vector 进行 sort，之后遍历判断是否和上一个元素相同。时间复杂度 O(nlogn)空间复杂度取决于 sort。
有一个更简单的写法是直接用 set 判断 size。

1
return set<int>(nums.begin(), nums.end()).size() < nums.size();

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        std::sort(nums.begin(),nums.end());
        int temp = 0;
        for(size_t i = 0; i < nums.size(); i++){
            if(i == 0){
                temp = nums[0];
            }
            else{
                if(nums[i] == temp)
                    return true;
                else
                    temp = nums[i];
            }
        }
        return false;
    }
};
,
  1. 3 月 8 日 每日一题
    1. 题目：217. Contains Duplicate
    2. 思路
    3. 代码