219. Contains Duplicate II

Intuition

일단 이중 for문을 쓰면 안 될 것 같다(너무 써보라고 하는 것 같아서 안 쓰고 싶다)
어차피 시간복잡도는 최소 O(n)이 되어야 하니 (array니까) 걱정하지 말자

아이디어 1: 숫자쌍 우선 찾기
1. nums에서 1번 조건에 부합하는 숫자쌍을 찾는다
2. 숫자가 문제 이해의 2번 조건(2. abs(i - j) <= k: i-j의 절댓값이 k보다 작다.)를 만족하는지 체크한다.
3. 맞으면 true, 다 돌 때까지 없으면 false 리턴

• 문제점: 1번-숫자쌍 찾기 과정에서 어떻게 효율적으로 찾을 수 있을까?

아이디어 1의 1번 구체화시키기
크기가 k인 배열? 아무튼 어떤 자료구조가 있다고 하자.
1. k 크기만큼만 nums를 조회?한다
2. 범위 내에서 아이디어 1-2번을 진행한다.
=> 그럼 결국 k 크기의 배열이나 그런 걸 생성해서 큐 방식으로 하나씩 내보내면서 가면 될 듯!

Approach

1. k 크기의 큐(자료구조 어떤 걸 써야 하지)를 진행할 공간을 만든다
2. 큐에다가 index k+1번째까지 값들을 넣으면서 문제의 1번 조건(1. nums[i] == nums[j]: 두 값이 같다)에 해당하는지 확인한다.
3. 이제 한 칸씩 큐를 움직이면서(실제로는 값을 하나 pop하고 하나 넣으면서) 확인한다.

• 고민인 점: 이렇게 되면 O(n^2) 시간복잡도를 가지게 되는 거 아닐까 -> 문제의 1번 조건에 맞는지 확인하는 방법을 O(1)로 진행하면 된다. hashMap을 써도 nums에서 index 정보를 조회할 수 있으므로, 괜찮을 것 같다.
• 어려웠던 부분: HashMap을 사용하는 발상까지는 좋았으나, 순서 관련 내용을 넣어도 HashMap 특성상 같은 key값이 존재한다면 value가 가장 최신의 것으로 덮어씌워진다. 따라서 범위 내에 index가 존재하는지 확인하기 어려웠다.
  -> 문제의 2번 조건(2. abs(i - j) <= k: i-j의 절댓값이 k보다 작다.)을 활용하여 체크할 수 있었다.

Complexity

• Time complexity: O(n)

• Space complexity: O(n)

Code

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> que = new HashMap<>();
        for (int i =0; i<nums.length; i++){
            if (que.containsKey(nums[i]) && Math.abs(que.get(nums[i]) - i) <= k){ // 1번 조건 해당되는 경우 (=같은 값을 찾음)
                return true;
            }else{ // 1번 조건 미해당 (=같은 값을 찾지 못함)
                que.put(nums[i], i);             
            }
        }
        return false;
    }
}