[2주차] 219. Contains Duplicate II

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

LeetCode - The World's Leading Online Programming Learning Platform

---

📝 문제

1차원 정수배열 nums 와 정수 k 가 주어진다. nums[i] == nums[j] && abs(i - j) <= k 조건을 만족하는 두 원소가 존재하면 true, 아니면 false 를 반환하라.

 

🎈 풀이

시간복잡도: O(n)

공간복잡도: O(n)

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;
        } else {
            map.put(nums[i], i);
        }
    }

    return false;
}

 

 

Index 0~2 까지 진행하며 Map에 값과 인덱스를 저장하였다.

Index 3 에선 Key 가 충돌하므로 해당 Key의 index를 가져와서 k 범위 내인지 확인한다.

3 - 0 = 3 , 3 > k 이므로 조건에 맞지 않는다.

0번 인덱스에 존재하는 1은 이제 더 이상 다른 1 과 인접한 k 범위 내에 들 수 없다. 따라서 1의 Index를 3으로 교체한다.

 

 4 - 1 = 3, 3 > k 이므로 조건에 맞지 않는다. 2의 인덱스를 4로 교체한다.

 

 

5 - 3 = 2, 2 <= k 이므로 조건에 성립한다. 따라서 true 를 리턴한다.