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.

풀이

• map은 key=요소 값, value=인덱스
• nums[i] == nums[j]는 map에 현재 요소 값이 존재할 때
• abs(i - j) <= k는 현재 인덱스에서 map에서 가져온 nums[i]의 예전 인덱스가 k보다 작거나 같은지 비교
• 그 외의 경우 map에 추가

수도코드

dic = dict()
for nums 처음부터 끝까지:
	if nums[i] in dic and i - dic[nums[i]] <= k:
    	return True
     dic에 (nums[i], i) 추가
return False  # no case

Solution(Runtime: 50ms)

import java.util.*;


class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, List<Integer>> map = new HashMap<>();

        for(int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], new ArrayList<>());
            }
            List<Integer> indexs = map.get(nums[i]);
            indexs.add(i);
            map.put(nums[i], indexs);
        }

        for(var key: map.keySet()) {
            List<Integer> arr = map.get(key);
            for(int i = 1; i < map.get(key).size(); i++) {
                if (Math.abs(arr.get(i - 1) - arr.get(i)) <= k) {
                    return true;
                }
            }
        }
        return false;
    }
}

Solution(Runtime: 17ms)

import java.util.*;

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
                return true;
            }
            map.put(nums[i], i);
        }

        return false;
    }
}

처음에는 map에 nums[i]를 key로, nums[i]를 값으로 갖는 인덱스를 리스트로 저장해 저장된 인덱스를 하나하나 비교하는 방식으로 구현하였다.

하지만, 미리 모든 데이터를 분류할 필요 없이 map을 활용하여 현재의 값과 저장된 다른 하나의 값을 비교하는 온라인 알고리즘으로도 풀이가 가능하다.