[Sliding Window Fixed Size] 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

 

최종 코드

브루스 포스 => 풀리지만, 타임 제한에 걸림!!

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        
        for l in range(len(nums)):
            for r in range(1, len(nums)):
                if l != r and nums[l] == nums[r]:
                    if abs(l-r) <= k:
                        return True 
        return False

 

슬라이딩 윈도우 매커니즘을 사용했지만, 타임제한에 걸림 ==> 해시맵 사용해야 함!

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # abs(i - j) <= k : 슬라이딩 윈도우 사이즈가 k 이하 라는 의미
        for i in range(len(nums)):
        	# 현재 인덱스 i 이후의 k개만 확인
            # 현재 인덱스 i에 대해, 다음 인덱스 i+1부터 i+k까지를 확인
    		# 단, 배열을 벗어나지 않도록 min(i+k+1, len(nums))로 자름
            for j in range(i+1, min(len(nums), i+1+k)):
                if nums[i] == nums[j]:
                    return True
                
        return False

 

해쉬맵 사용

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # abs(i - j) <= k : 슬라이딩 윈도우 사이즈가 k 이하 라는 의미
        # 숫자와 해당 숫자가 마지막으로 등장한 인덱스를 저장하는 딕셔너리
        hashmap = {} # n: idx

        for i, n in enumerate(nums):
            # n in hashmap 조건 만족하면, 2번째 n 임
            # 현재 숫자가 hashMap에 존재하고, 인덱스 차이가 k 이하인지 확인
            if n in hashmap and abs(i-hashmap[n]) <= k:
                return True   

            # 현재 숫자와 인덱스를 hashMap에 저장하거나, 기존 값을 업데이트                         
            hashmap[n] = i

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