[Java] 219. Contains Duplicate II

문제 파악

정수 배열인 nums 에서 두 인덱스의 차이가 k 이하이면서 값이 같으면 true를 반환하고 없다면 false를 반환해야한다.

 

---

풀이

 

1️⃣ Map을 이용한 풀이

 

💡 떠오른 Idea

nums를 순회하면서 map에 값을 key로 인덱스를 value로 저장하고, map에 이미 존재하면 현재 위치와 map에 저장되어 있는 인덱스의 차이를 구해서 비교해본다.

만약, 인덱스간 차이가 k보다 크다면 map을 갱신해준다. 왜냐하면 이후에 인덱스 차이가 k 이하인 경우가 생길 수 있기 때문이다.

 

import java.util.*;

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int N = nums.length;
        for (int i = 0; i < N; i++) {
            int num = nums[i];
            if (map.containsKey(num)) {
                int idx = map.get(num);
                if (i - idx <= k) {
                    return true;
                } else {
                    map.put(num, i);
                }
            } else {
                map.put(num, i);
            }
        }
        return false;
    }
}

 

결과

 

---

📖 회고

HashMap의 특징만 잘 활용하면되는 간단한 문제였다.