[리트코드] 219. Contains Duplicate II

문제

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

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

Contraints:

 

• 1 <= nums.length <= 10**5
• -109 <= nums[i] <= 10**9
• 0 <= k <= 10**5

---

✔ 문제접근 #1 해시[통과] ⭕

Intuition
해시를 이용하여 가장 최근에 나왔던 같은 값의 index를 보관해준다.

Algorithm

dict자료구조 h를 선언하고, 전체 배열을 순회한다.만약 요소가 h에 있다면 문제 조건과 일치하는지 검사하고 조건과 일치한다면 반환한다.만약 그렇지 않다면 현재 요소를 key, 위치(index)를 value로 하여 h에 저장한다.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        
        h = dict()
        for i in range(len(nums)):
            elem = nums[i]
            
            if elem in h:
                if abs(h[elem] - i) <= k:
                    return True
                
            h[elem] = i
            
        return False

 

Complexity Analysis

• 시간 복잡도 : O(N)
  • 배열을 순차탐색 O(M)
  • dict자료구조의 in 연산 O(1)
  • 그러므로 전체시작복잡도 : O(N*1) = O(N)

• 공간복잡도 : O(N)
  
  • dict 자료구조 사용

---

기타풀이 및 회고

문제에서 k값 이내의 거리에 있어야하기 때문에 중복 요소가 나왔을 때 이전에 나왔던 요소의 위치를 무시하고 dict자료구조에 새로 덮어쓰기해도 상관없다. 기존에 저장되어있는 값보다 새로 들어온 값이 뒤에서 순회할 요소와 더 가깝기 때문이다.