219. Contains Duplicate II (Array, Hash Table, Sliding Window)

링크 - https://leetcode.com/problems/contains-duplicate-ii/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

1) Hash Table

Hash table에 각 글자의 index를 보관하는 식으로 푸는 방법이다.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        hash_table = {}
        for i, num in enumerate(nums):
            if num in hash_table and i - hash_table[num] <= k:
                return True
            else:
                hash_table[num] = i

        return False

Time Complexity: O(n) nums를 다 돌기 때문이다.

Space Complexity: O(n) 최대 n개의 원소를 hash_table에 담을 수 있기 때문이다.

2) Hash Set

Hash set을 사용해 최대 k개의 글자만 보관하고 num이 포함되면 true를 반환하는 방법이다.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        num_set = set()
        for i, num in enumerate(nums):
            if num in num_set:
                return True
            else:
                num_set.add(num)
                if len(num_set) > k:
                    num_set.remove(nums[i-k])

        return False

Time Complexity: O(n) nums를 다 돌기 때문이다.

Space Complexity: O(n) 최대 n개의 원소를 hash_table에 담을 수 있기 때문이다.