[LeetCode] 219. Contains Duplicate II - Java

Contains Duplicate II - LeetCode

 

문제

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

 

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

 

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

 

정수 배열 nums 와 정수 k 가 주어졌을 때

nums[i] == nums[j] 와 abs(i - j) <= k 를 모두 만족하는 서로 다른 i와 j가 존재하면 true, 존재하지 않으면 false를 반환한다.

 

---

 

내 풀이

HashMap 사용

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {

        boolean answer = false;
        Map<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i<nums.length; i++){
            int num = nums[i];
            if(map.containsKey(num) && Math.abs(map.get(num) - i) <= k){
                answer = true;
                break;
            }
            map.put(num, i);
        }
        return answer;

    }
}

해시 맵을 사용하여 중복된 숫자의 인덱스를 기록했다.

map 은 nums 요소를 key로, 해당 요소의 인덱스를 value로 저장한다.

 

nums 요소를 순회하며

• 맵에서 조건을 만족하는 키가 있는지 검사하고 있으면 반복문을 종료하고 true를 반환한다.
• 인덱스이 차이가 적게 나는 것이 조건을 만족할 확률이 높기때문에 맵의 value를 업데이트 해준다.

 

반복문이 끝날때 까지 조건을 만족하는 키가 존재하지 않는다면 초기값 그대로 false를 반환한다.

 

• 시간복잡도 : O(n) - 배열 순회
• 공간복잡도 : O(n) - 해시 맵의 크기에 비례

 

---

 

다른 사람의 풀이

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {

      HashMap<Integer, Integer> cache = new HashMap<>();
      int length = nums.length;

      for (int i = 0; i < length; i++) {
        Integer prev = cache.put(nums[i], i); // 맵에 value를 업데이트하면서 바로 이전 value를 받아옴
        if (prev != null && i - prev <= k) {
          return true;
        }
      }

        return false;
  }
}

해시맵을 사용해 같은 흐름으로 푼 코드이지만 맵에 키와 value를 저장하면서 바로 이전의 value를 받아오고 있다.

 

HashMap의 put() 메서드는 다음과 같은 구조를 가지고 있다.

• V put(K key, V value)
• 키가 이미 맵에 존재한다면 이전 value를 반환하고, 맵에 없는 경우 null을 반환한다.

 

각각의 메서드가 어떤 파라미터와 리턴을 갖는지 정확히 알고 사용한다면 더 효율적인 코드를 작성할 수 있다.