[LeetCode/Java] 219. Contains Duplicate II

0. 문제

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

1. 문제 설명

• 정수 배열 nums와 정수 k가 주어진다.
• nums 배열 안에 아래의 조건을 만족하는 두 개의 다른 인덱스 i와 j가 존재한다면 true를 반환하라.
  • nums[i]와 nums[j]가 같아야 한다.
  • i - j의 값이 k 이하다

2. 문제 풀이

2.1. 접근법 : 해시맵

• nums를 탐색한다.
• 만약 nums[현재 인덱스]의 값을 Key로 가지면서 현재 인덱스 - nums[현재 인덱스]의 Value가 k보다 작다면 true를 반환한다.
• nums의 탐색이 끝났는데 위 조건을 만족하는 Key-Value를 못 찾았다면 false를 반환한다.

3. 코드

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;
    }
}

4. 결과

5. 개선점

5.1. 시간 복잡도 개선

• Map의 put 메서드는 반환값이 있다.
• 새로운 Key 값이면 null을 반환한다.
• 이미 존재하는 Key 값으로 새로운 Value를 put할 때 기존의 Value를 반환한다.
• 이를 이용하면 다음과 같은 풀이가 가능하다.
  • nums를 탐색한다.
  • map에 numsi와 i(인덱스)를 넣고 반환값을 구한다.
  • 만약 반환값이 존재하고(이전에 등장한 값) 현재 인덱스(i) - 반환값(이전에 등장했던 인덱스)가 k보다 작으면 true 반환
• 풀이

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
      HashMap<Integer, Integer> map = new HashMap<>();
      int length = nums.length;
      for (int i = 0; i < length; i++) {
        Integer prev = map.put(nums[i], i);
        if (prev != null && i - prev <= k) {
          return true;
        }
      }
    return false;
  }
}

• 결과