[leetcode] 219. Contains Duplicate II

Contains Duplicate II

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

 

Example 1:

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

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

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

 

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

 

풀이 - 1

function containsNearbyDuplicate(nums: number[], k: number): boolean {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      if (i === j) {
        continue;
      }
      if (nums[i] === nums[j] && Math.abs(i - j) <= k) {
        return true;
      }
    }
  }

  return false;
}

무식하게 구현하니 무식한 숫자가 당황스럽게 했다.. 역시 최적화가 필요하다..

 

풀이 - 2

function containsNearbyDuplicate(nums: number[], k: number): boolean {
  const obj: { [key: number]: number } = {};

  for (let i = 0; i < nums.length; i++) {
    if (obj[nums[i]] && Math.abs(obj[nums[i]] - i) <= k) {
      return true;
    }

    obj[nums[i]] = i;
  }

  return false;
}

시간복잡도 O(n)에 맞게 코드를 짜보았는데 nums = [1, 2, 3, 1],  k = 3의 케이스에서 true를 반환해야하는데 false를 반환하여 오답처리되었다.

아마 키값으로 먼저 들어간 1이 나중에 들어가는 1의 값과 다르다고 인식되어 생기는 문제로 추정된다..

 

풀이 - 3

function containsNearbyDuplicate(nums: number[], k: number): boolean {
  const hashMap: Map<number, number> = new Map<number, number>();

  for (let i = 0; i < nums.length; i++) {
    if (hashMap.has(nums[i]) && Math.abs(hashMap.get(nums[i])! - i) <= k) {
      return true;
    }

    hashMap.set(nums[i], i);
  }

  return false;
}

풀이 - 2와 유사한 로직에서 자료구조만 Map을 사용하였는데 Object는 안되고 Map은 되는 자세한이유를 알아보아야겠다..