문제

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

해결 방법

• nums[i] == nums[j], abs(i - j) <= k 이 2가지 조건을 만족하는 두개의 값이 존재하는지 체크하는 문제
• nums[i]가 x라고 가정해보면, 이 때 필요한 값은 i 이전에 가장 최근 나온 x의 index만 알면 됨
• 따라서, nums의 값을 key로 가진 HashMap을 사용하여 해결 가능
  • nums[i]를 key로 가진 것이 없다면 HashMap에 (nums[i], i) 삽입
  • nums[i]를 key로 가진 것이 있다면 value값과 i의 차이가 k 이하인지 체크
    • k 이하라면 true return
    • k 초과라면 (nums[i], i) 삽입 (이전에 nums[i] 위치는 더 이상 필요 없기 때문)

코드

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

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

                map.put(num, i);
            }
        }

        return false;
    }
}

결과