[Leetcode] 219. Contains Duplicate II - JS

https://leetcode.com/problems/contains-duplicate-ii/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- 정수배열 nums, 정수 k 주어질 때 서로 다른 index i,j에 대하여 아래 두 조건을 만족하는지 판단하라.

1. nums[i] == nums[j]
2. abs(i - j) <= k

제한조건
--------------------
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- 0 <= k <= 10^5

 

2. 접근 방법

접근방법
--------------------
abs(i - j) <= k 조건은 결국 i < j라고 가정할 때
i와 j의 차이가 k보다 작거나 같아야 한다.
즉, i 인덱스에서 k까지의 거리 사이의 인덱스에서
조건 1 nums[i] == nums[j]인 요소가 있는지 확인하면 된다.

i 인덱스를 기준으로 이후 k까지의 범위 내에서 j인덱스를 찾는 것은
nums.length, k = 10^5일 경우, 시간 복잡도가 너무 느리다.

해쉬 맵을 사용하여 각 요소의 해당하는 인덱스 배열을 할당한 다음,
할당할 때, abs(i - j) <= k를 만족하는게 있는지 확인한다.

 

 

3. 코드

var containsNearbyDuplicate = function(nums, k) {
    const hash = {};
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (!hash[num]) {
            hash[num] = []
        }
        hash[num].push(i);
    }

    const values = Object.values(hash).filter(val => val.length > 1);
    
    for (let val of values) {
        let i = 0;
        let j = 1;
        while (i < val.length) {
            if (j === val.length) {
                i++;
                continue;
            }
            if (Math.abs(val[i]-val[j]) <= k) {
                return true;
            } else if (Math.abs(val[i]-val[j]) > k) {
                i++;
                j = i + 1;
                continue;
            }
            j++;
        }
    }
    return false;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

해쉬맵을 사용한 뒤 중복되는 값들의 인덱스를 배열로 관리했다.

인덱스 배열 중 길이가 2 이상인 것들만 필터링 해주고

필터링 된 인덱스 배열들을 순회하면서 abs(i - j) <= k를 만족하는 조건을 찾기위해 Two pointer를 사용하였다.

시간 복잡도는 O(n)이 나오긴 하지만, 코드가 너무 복잡하다.

 

왜냐하면 불필요하게 인덱스 배열을 가지면서 필터링 기능과 Two pointer를 사용하였기 때문이다.

이러한 불필요한 과정을 제거하기 위해 해쉬맵에 해당 숫자의 인덱스 값을 갖도록 하고

이미 해쉬에 등록된 경우 이전 인덱스와 현재 인덱스를 가지고 abs(i - j) <= k 조건을 확인하는 방법으로 개선해보았다.

 

5. 가독성 좋은 코드로 개선

var containsNearbyDuplicate = function(nums, k) {
    const hash = {};
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (Math.abs(hash[num] - i) <= k) {
            return true
        }
        hash[num] = i
    }
    return false;
};

이미 hash에 저장된 요소의 인덱스와 현재 인덱스를 가지고 abs(i - j) <= k 조건을 확인한다.

hash에 요소의 인덱스를 갱신한다.

i, j 두 인덱스만 확인하면 되니 굳이 중복되는 요소의 모든 인덱스를 배열로 가지고 있을 필요가 없다.

 

첫번째 순회 시 Math.abs(undefined - 0) <= k 조건에서, Math.abs(undefined - 0) == 'NaN'이므로 올바른 비교는 아닐 수 있다.

결과적으로  Math.abs(undefined - 0) <= k 값이 false가 나오므로 그대로 진행했다.

정확히 하기 위해선 hash[num] !== undefined 조건을 추가해주는 것이 옳다.