[LeetCode] 219. Contains Duplicate II

Contains Duplicate II - LeetCode

int 배열과 int가 주어지면 boolean을 반환하는 문제입니다.

nums[i] == nums[j] and abs(i - j) <= k라면 true, 아니면 false를 반환합니다.

 

Example 1:

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

Example 2:

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

 

문제접근

1. 브루트포스

처음에는 당연히 브루트포스 접근하였습니다.

하지만 nums의 길이가 10의 5승이기때문에 2중 loop를 사용할 수 없다고 판단하였습니다.

 

2. 투포인터

배열안에서 두개의 값을 확인하는것이니 투포인터가 적절하다고 생각했습니다.

하지만 투포인터도 사용하기 어려웠습니다.

정렬되지 않은 배열이기 때문입니다.

 

2. 해시테이블

TwoSum의 문제처럼 해시테이블을 활용해서 풀어볼 수 있다고 생각했습니다.

해시테이블로 배열안의 두개의 값을 비교할 수 있다고 생각했기 때문입니다.

 

2개가 중복이라는 것은 어떻게 판단하지??

2개가 있다고 판단하는것은 지금 바라보는 요소를 해시테이블에 put할때 이미 있다면?

중복되는 요소라는 뜻입니다.

public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            Integer cur = nums[i];
            if (map.containsKey(cur) && i - map.get(cur) <= k) {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }

 

시간복잡도

사용하는 해시테이블의 메서드는 O(1)의 시간복잡도를 갖고있습니다.

nums를 한번 반복하고 있으니 O(n)의 시간복잡도가 필요합니다.

 

느낀점

해시테이블은 int값의 배열에서 두수를 비교할 수 있을때도 사용할 수 있다는것을 꼭 기억해야겠습니다.