219. Contains Duplicate II

LeetCode Link (opens in a new tab)

Sliding Window Hash Table

Description

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 cases

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 $<= 10^5$
• $-10^9 <=$ nums[i] $<= 10^9$
• $0 <=$ k $<= 10^5$

Approach

sliding window를 사용하여 해결할 수 있다.
l은 sliding window의 시작 인덱스이고 r은 sliding window의 끝 인덱스이다.
l과 r을 0으로 초기화하고 r을 1씩 증가시키며 nums[r]을 해시테이블에 추가한다.
해시테이블에 이미 존재하는 값이라면 바로 true를 반환하면서 종료하면 되고, 해시테이블의 크기가 k보다 크다면 map에서 nums[l]을 삭제하고 l을 1 증가시킨다.
이런식으로 해시테이블의 크기를 k로 유지하면서 시작 인덱스인 l과 k를 더한 값이 배열의 길이보다 작거나 같을 때까지 배열을 순회한다
테스트케이스에서 k가 배열의 길이보다 큰 경우가 있는데, constraints에도 k값이 nums.length보다 작거나 같다는 별도의 조건이 없기 때문에, k와 nums.length중 작은 값을 k로 설정한다.

Solution Code

var containsNearbyDuplicate = function(nums, k) {
    const map = new Map()
    let l = 0
    let r = 0
    k = Math.min(nums.length, k)
    while (l + k <= nums.length) {
        if (map.has(nums[r])) {
            return true
        } else {
            map.set(nums[r], true)
            r += 1
        }
        if (map.size > k) {
            map.delete(nums[l])
            l += 1
        }
    }
 
    return false
};

Complexity

• time complexity : $O(n)$
• space complexity : $O(k)$