[Leetcode/파이썬] 219. Contains Duplicate II

Contains Duplicate II

---

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

 

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        """
        n = 10 ** 5
        k = 10 ** 5 
        O(n) 으로 끝내야함. 
        """
        n = len(nums)
        target = {}

        for idx in range(n) :
            if nums[idx] in target and idx - target[nums[idx]] <= k :
                return True

            target[nums[idx]] = idx
        return False

Leetcode의 1번 문제 2Sum과 유사한 문제가 나왔다. 이번엔 인덱스로 접근하는 문제였다. 

$O(n \times k)$ 는 $10 ^ 10$ 이 되기 때문에 적합한 문제 해결 방법이 아닐 것이다. 그러면 어떻게 해결해야 하나...

힌트 부분을 참고하였다. Hash Table이 있길래 아 이거다. 생각했다. 

현재 값이 해시 테이블에 존재하지 않으면 키-값을, (현재값) : (인덱스) 로 해시 테이블에 추가한다. 여기서 우리는 k값에 대해 생각할 필요가 있다. 현재의 위치에서 k 값 만큼 안에 동일한 값이 있는지 판단해야 하기 때문에 안에 들어간 값의 인덱스와 현재의 인덱스가 k 값 안에 들어와야 한다.

따라서 if 문은

1. 현재 위치의 값과 동일한 값이 해시 테이블 안에 있는지
2. 현재 위치와 동일한 값의 위치가 k 범위 안에 있는지

를 같이 판단해줘야 한다. 아니라면 추가. 이걸 정리하면 위 코드 처럼 구현할 수 있다. 

오랜만에 풀다 보니 이거저거 다 참고했는데 어떻게 흘러가는지는 쉽게 판단할 수 있었다.