[LeetCode][Python] 217. Contains Duplicate

 

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

난이도 Easy

주어진 배열에서 중복된 값이 있으면(=2번 이상 등장하는 값이 있으면) True, 아니면 False 반환하는 문제

 

풀이 방식이 여러가지 있다

(1) brute force -> 모든 (i, j) 조합을 검사한다 -> O(n^2) -> timeout

(2) 정렬 -> 정렬한 뒤 한번 순회한다 -> 정렬하니 O(nlogn)

(3) hash set -> 하나씩 hash map 또는 set에 넣는다. 넣기 전에 이미 있는지 검사한다. -> O(n)

 

가장 효율적인건 해시 방식이다

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False