LeetCode 210(Contains Duplicate II, Python)

1. 문제 링크 

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

Contains Duplicate II - LeetCode

 

2. 문제 설명

• 정수로 구성된 array nums와 정수 k가 주어졌을 때, 두개의 distinct한 i,j 에 대해 nums[i] == nums[j]이면서 abs(i-j) <=k를 충족하면 True, 아니면 False를 반환
• 즉, index i,j사이의 거리가 k보다 작거나 같으면서, i,j의 값이 같은게 존재하면 True, 아니면 False를 반환하는 문제 
• 예시1) nums = [1,2,3,1], k=3 이면, i=0, j=3일 때의 값이 1로 동일하고, 둘 사이의 거리는 3으로 3보다 작거나 같으므로 True반환
• 예시2) nums = [1,0,1,1], k=1 이면, i=2,j=3일 때의 값이 1로 동일하고, 둘 사이의 거리는 1으로 1보다 작거나 같으므로 True반환
• 예시3) nums = [1,2,3,1,2,3], k=2이면 거리가 2보다 작거나 같을 때, 동일한 값은 존재하지 않으므로 False 반환 

3. 처음 풀이

• hash table 사용하기
• nums의 값을 key, index를 value로 하는 hist라는 dict을 만들고
• nums에 대해 for문을 돌리면서, 해당 값이 hist에 포함되있으면서, 둘 사이의 Index거리가 k보다 작거나 같으면 True를 반환하고,
• 그렇지 않으면 False를 반환

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:

        hist = {}
        for index, i in enumerate(nums):
            if i in hist and index - hist[i] <= k:
                return True
            hist[i] = index
        
        return False

 

4. 다른 풀이

• submission된 다른 풀이를 봐도 대부분, hash table로 접근한 것 같다. 
• 아래는 dict 대신 set()을 사용한 풀이
• window라는 집합의 개수를 k개보다 작거나 같게 유지하면서, 해당 값이 window에 포함되어있는지의 유무를 체크한 방식. 

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