LeetCode - Contains Duplicate II

💡Contains Duplicate II

✔️ 문제 링크

https://leetcode.com/explore/learn/card/hash-table/184/comparison-with-other-data-structures/1121/

처음에는 for문을 돌면서 nums의 i번째 인덱스 이후에 nums에 nums[i]가 있는지 확인하고 있다면 다시 for문을 돌면서 j-i가 k보다 작은게 있으면 return true해주려고 했다.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    let len = nums.length;
    
    for(let i = 0; i<len; i++){
        let num = nums[i];
		if(nums.includes(num, i+1){
        	for(let j = i+1; j<len; j++){
        		if(nums[j] === num && j-i <=k) return true;
        	}   	
        }
    }
    return false;
};

• 예상은 했지만 역시나 time out!
• 다른 방법을 사용해야했다

Map을 이용하여 해결

javascript는 [키,값]의 구조를 가진 Map객체를 생성할 수 있다.
Map을 이용해 해결했다

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    let numMap = new Map();
    let len = nums.length;
    
    for(let i = 0; i<len; i++){
        if(numMap.has(nums[i])){
            if(Math.abs(numMap.get(nums[i]) - i) <= k) return true;
        }
        numMap.set(nums[i], i);
    }
    return false;
};

numMap이라는 새로운 Map객체를 만들고 nums를 순회하면서 numMap에 해당 요소가 있는지 확인한다.
있을경우 중복값이기 때문에 확인절차를 거친다

numMap의 키값은 nums의 값이 되고, numMap의 값은 nums의 인덱스가 된다 => numMap.set(nums[i], i);
따라서 인덱스값을 비교해 절대값이 k보다 작으면 true를 리턴하고, 아니라면 다시 numMap의 값을 수정하게 된다.

예를들어 nums = [1,2,3,1,1,1]이고, k가 1이라고 하면 i가 2일때까지는 numMap = [1:0, 2:1, 3:2]이다.
i가 3이 되면 numMap에는 1이 이미 있기 때문에 if문을 거친다
numMap.get(nums[i]) 는 0이고, i는3이라 0-3의 절대값은 3이라 k보다 작거나 같지 않다.
따라서 numMap.set으로 인해 numMap = [1:3, 2:1,3:2]가 된다


이제 i가 4가 되면 numMap에는 역시 1이 있기 때문에 if문을 거친다
numMap.get(nums[i]) 는 3이고 i는 4라서 3-4의 절대값은 1이라 k와 같기 때문에 true를 리턴한다