[알고리즘/leetcode] Contains Duplicate(python)

set자료형을 사용했다. set 자료형은 해시 테이블로 구현되어 있기 때문에 시간 복잡도가 빠르다.

리스트 자료형에서 in을 이용하면 값을 일일이 확인하기 때문에 오래 걸린다. 하지만 set의 경우에는 해당 값을 해시 함수에 넣어 인덱스에 접근함으로써, 아주 빠르게 해당 값이 있는지 여부를 확인할 수 있다. 따라서 O(1)이 된다.

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