217. Contains Duplicate

중복된 문자가 있으면 true를 출력하기.

Solution

Set과 Dictionary로 풀면 O(n)이 나온다.

1. Dictionary 풀이

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        dic = {}
        for i in nums: # O(n)
            if i not in dic: dic[i] = True
            else: return True
        return False

2. Set 풀이

class Solution(object):
    def containsDuplicate(self, nums):
        s = set()
        for i in nums:
            if i in s: return True
            s.add(i)

        return False
        

시간 복잡도

둘 다 O(n).

공간 복잡도는 Set보다 딕셔너리가 10MB가 더 많이 나왔다.