219. Contains Duplicate II

219. Contains Duplicate II

 

해시맵 으로..

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        hashMap = {}  # 숫자와 해당 숫자가 마지막으로 등장한 인덱스를 저장하는 딕셔너리

        # nums 리스트를 순회하며 숫자와 인덱스를 처리
        for i, n in enumerate(nums):
            # 현재 숫자가 hashMap에 존재하고, 인덱스 차이가 k 이하인지 확인
            if n in hashMap and abs(i - hashMap[n]) <= k:
                return True  # 조건을 만족하면 True 반환

            # 현재 숫자와 인덱스를 hashMap에 저장하거나, 기존 값을 업데이트
            # 인덱스 차이가 k보다 작은 것을 찾기 때문에 항상 최신 인덱스로 갱신
            hashMap[n] = i  

        # 반복이 끝난 후에도 조건을 만족하는 숫자가 없다면 False 반환
        return False

 

 

셋(set) 으로..

 

https://youtu.be/ypn0aZ0nrL4?si=1Pq4mCraclMZzBId

 

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 현재 윈도우에 포함된 숫자를 저장하는 집합
        window = set()
        # 윈도우의 왼쪽 포인터
        L = 0

        # 리스트의 모든 요소를 순회 (R은 오른쪽 포인터)
        for R in range(len(nums)):
            # 윈도우 크기가 k를 초과하면, 왼쪽 포인터를 이동시키면서 윈도우 크기를 유지
            if R - L > k:
                window.remove(nums[L])  # 왼쪽 끝 요소를 윈도우에서 제거
                L += 1  # 왼쪽 포인터 이동
            
            # 현재 숫자가 이미 윈도우에 존재하면 조건 만족
            if nums[R] in window:
                return True

            # 현재 숫자를 윈도우에 추가
            window.add(nums[R])
        
        # 조건을 만족하는 숫자가 없으면 False 반환
        return False