219. Contains Duplicate II

문제

nums 배열에서 index가 k보다 작게 차이나는 값이 같은 두 요소를 찾자.

입력

• 정수 배열 nums
• 정수 k

출력

• true/false

---

나의 풀이

접근

비슷한 문제를 풀고 와서 어렵지 않게 푼 문제이다.

앞서 봤던 Two Sum 이라는 문제와 같이, 조건에 만족하는 두 개의 요소만 찾으면 된다. 따라서 똑같이 Hash Table 을 이용한 HashMap을 사용했다.

구현 코드

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<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;
    }
}

• (값, 인덱스) 이런 형태로 nums의 요소를 저장할 HashMap을 선언
• for문을 실행하며, nums의 요소 탐색
• 만약 map에 nums[i]의 키를 가진 데이터가 있고, 해당 키의 값과 i의 차이가 k보다 작거나 같다면, return true
• for문을 실행하는 동안 return 하지 않았다면 return false

결과

Time: O(n)

Space: O(n)

---

다른 풀이

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (k == 0) return false;

        Set<Integer> slidingWindow = new HashSet<>();
        for (int index = 0; index < nums.length; index++) {
            if (slidingWindow.contains(nums[index]))
                return true;
            if (index >= k)
                slidingWindow.remove(nums[index - k]);
            slidingWindow.add(nums[index]);
        }
        return false;
    }
}

이 풀이는 HashSet 을 이용해 Sliding Window 알고리즘 코드이다.

• 현재 탐색 요소는 window에 삽입
• 만약, window 안에 현재 탐색하고 있는 요소가 있다면 return true
• 현재 index가 k보다 크거나 같다면,
  • 이미 조건에서 주어진 k보다 더 멀리있는 전의 요소를 window에서 지운다.

사실 Hash Table을 사용한 개념은 같지만, 어떤 알고리즘을 사용하냐의 차이였고, 메모리나 실행 시간에서는 큰 차이가 없었다.