[Hash Table] Contains Duplicate II

219. Contains Duplicate II

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 
 * Runtime	: 115 ms
 * Memory	: 63.05 MB
 */
var containsNearbyDuplicate = function(nums, k) {
  const hash = {};

  for(let i = 0; i < nums.length; i++) {
    const num = nums[i];

    if(hash[num] > -1 && Math.abs(hash[num] - i) <= k) {
      return true;
    }

    hash[num] = i;
  }

  return false;
};

Example 1을 예로

Input: nums = [1,2,3,1], k = 3
Output: true

루프 마다 해시 테이블의 상태는 다음과 같습니다.

1번째 루프:	{ '1': 0 }
2번째 루프:	{ '1': 0, '2': 1 }
3번째 루프:	{ '1': 0, '2': 1, '3': 2 }

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using sliding window

해답의 전문은 링크를 확인해주세요.

/*
 * Runtime	: 84 ms
 * Memory	: 55.62 MB
 */
var containsNearbyDuplicate = function(nums, k) {
  let set = new Set(); // create set so we can keep track of all nums in our window
  let left = 0;
  for (let right = 0; right < nums.length; right++) {    
    // if our window is bigger than k, move left pointer to shrink window
    if ((right - left) > k) { 
      set.delete(nums[left]); //don't forget to remove num from set before updating left pointer
      left++; // update left pointer
    }
    
    if (set.has(nums[right])) return true; // if we see the same num twice within our window, return true
    else set.add(nums[right]); // else add curr num to set to mark as visited
  }
  return false;
};

런타임 사용측면에서 필자보다 나은 성능을 보여준 해답입니다.