[알고리즘] LeetCode - Contains Duplicate II

Contains Duplicate II - LeetCode

문제 설명

• 정수형 배열 nums가 주어진다.
• nums의 같은 두 수의 사이 간격이 k보다 작은 경우가 있으면 true, 없으면 false를 반환한다.

문제 해결

• 반복문을 앞에서부터 수의 값을 Key로 인덱스를 Value로 하도록 HashMap에 계속해서 갱신한다.
• 현재 수의 값과 동일한 Key를 가진 값이 있는 경우 현재 인덱스와 HashMap의 인덱스를 빼서 같은 두 수간 거리를 구한다.
• 이후 k보다 작거나 같은 경우가 있으면 true를 반환하고 없으면 반복문을 다 돌고 false 반환한다.

시간 복잡도

• O(N)

풀이 코드

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int N = nums.length;

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int now = nums[i];
            if (map.containsKey(now)) {
                int j = map.get(now);
                int d = i - j;
                if (d <= k) {
                    return true;
                }
                map.put(now, i);
            } else {
                map.put(now, i);
            }
        }

        return false;
    }
}

결과

시간	메모리
17 ms	56.4 MB