[Leetcode] 217. Contains Duplicate 문제풀이

https://leetcode.com/problems/contains-duplicate/

Contains Duplicate - LeetCode

 

문제 내용

배열에서 중복된 값이 있는지 검사하는 문제

 

Example 1:

Input: nums = [1,2,3,1]

Output: true

 

문제 풀이

hash를 이용해서 값을 메모해놓고

hash값이 있으면 true를 반환하면 된다.

 

그런데 이상하게 sort 하고 검사하는것보다 속도가 늦게 나온다..

sort하면 O(nlogn) 이고 hash로 하면 O(n) 이라고 생각했는데 그게 아닌가...

map 안에서 뭐 많이 하나보다

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        map<int,int> hash;
        for (auto num : nums) {
            hash[num]++;
            if (hash[num] == 2) {
                return true;
            }
        }
        return false;
    }
};