[Leetcode/Sliding Window, HashMap] 219. Contains Duplicate II

첫번째 방법 - 해시맵(HashMap)

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        index_map = {}  # 숫자의 마지막 등장 인덱스를 저장할 딕셔너리

        for i, num in enumerate(nums):
            if num in index_map and i - index_map[num] <= k:
                return True
            index_map[num] = i  # 현재 숫자의 인덱스를 업데이트
        
        return False

딕셔너리(HashMap)을 사용하여 숫자의 인덱스를 저장하고,
현재 인덱스와 이전에 나온 동일 숫자의 인덱스 차이가 k 이하인지 확인하는 방식.

풀이 설명

1. index_map 딕셔너리를 사용하여 숫자 num의 가장 최근 인덱스를 저장한다.
2. 리스트 nums를 순회하면서:
   • 현재 숫자가 index_map에 존재하는지 확인한다.
   • 존재한다면, 현재 인덱스 i와 저장된 인덱스 index_map[num]의 차이가 k 이하인지 검사한다.
   • k 이하라면 True를 반환한다.
   • 아니라면, 현재 숫자의 인덱스를 업데이트한다.
3. 전체 탐색이 끝난 후에도 조건을 만족하는 경우가 없다면 False를 반환한다.

시간 복잡도

• O(N): 리스트를 한 번 순회하면서 딕셔너리를 이용해 조회 및 갱신 작업을 수행하므로, 평균적으로 O(1) 연산이 소요되어 전체적으로 O(N)의 시간 복잡도를 가진다.

---

두번째 방법 - 슬라이딩 윈도우(Sliding Window)

고정된 크기의 윈도우를 유지하면서 중복된 요소를 찾는다!

풀이 방법

1. 윈도우 크기 k를 유지하는 Set을 활용:
   • Set을 사용하여 현재 윈도우 내에 존재하는 요소들을 저장한다.
   • 중복 요소가 발견되면 True를 반환한다.
2. 윈도우의 크기를 k로 유지:
   • 현재 인덱스가 k를 초과하면 가장 오래된 값을 제거하여 윈도우 크기를 유지한다.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = set()  # 현재 슬라이딩 윈도우 내의 숫자 저장

        for i, num in enumerate(nums):
            if num in window:
                return True  # 중복 발견

            window.add(num)  # 현재 숫자를 윈도우에 추가

            if len(window) > k:  # 윈도우 크기를 k로 유지
                window.remove(nums[i - k])  # 가장 오래된 요소 제거

        return False  # 중복이 없는 경우

풀이 설명

• set()을 사용하여 현재 윈도우에 있는 요소들을 저장한다.
• 리스트 nums를 한 번 순회하면서:
  1. 현재 숫자가 set에 존재하면 중복 발견 → True 반환.
  2. 숫자를 set에 추가.
  3. set 크기가 k를 초과하면 가장 오래된 숫자를 제거하여 슬라이딩 윈도우 크기를 유지.
• 전체 탐색이 끝난 후에도 조건을 만족하는 경우가 없다면 False를 반환한다.

시간 복잡도

• O(N): set의 삽입/삭제 연산은 평균적으로 O(1)이므로 전체적으로 O(N)의 시간 복잡도를 가짐.

슬라이딩 윈도우 방식의 장점

✅ 딕셔너리 기반 방식보다 메모리 사용이 적음: 불필요한 인덱스 저장 없이, set만 사용하여 윈도우를 관리함.
✅ 실행 속도가 빠름: set의 삽입/삭제 연산이 평균 O(1)이므로 효율적.