219. Contains Duplicate II

리트코드 219번 풀이

문제

Contains Duplicate II

풀이

아이디어

k 범위 안에 중복된 숫자가 있는지 확인하는 문제이다. 범위를 계속 움직여야 하기 때문에 슬라이딩 윈도우!

중복을 확인하기 위해 Set을 이용하고, k 범위만 확인하기 위해서 set의 크기 (슬라이딩 윈도우의 크기)가 k보다 커지면 가장 오래된 숫자를 제거해줬다. (슬라이딩 윈도우를 오른쪽으로 옮겨주는 효과)

코드

function containsNearbyDuplicate(nums: number[], k: number): boolean {
  const set = new Set();
  for (let idx = 0; idx < nums.length; idx++) {
    if (set.has(nums[idx])) return true;
    set.add(nums[idx]);
    if (set.size > k) set.delete(nums[idx - k]);
  }

  return false;
}

시간 / 공간 복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(k)