LeetCode Top Interview 150) Contains Duplicate II

Question

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.

Constraints:

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

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:

---

---

정렬되지 않은 정수 리스트 nums에서, 정수 k만큼의 길이를 가지는 연속된 일부분이 같은 값을 가지는지 bool값으로 반환하는 문제입니다.

제가 생각한 코드는 다음과 같습니다.

from collections import defaultdict

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        if k==0: 
            return False
        d = defaultdict(int)
        
        for i in range(len(nums)):
            if nums[i] in d:
                return True

            d[nums[i]] = i
            
            if i>=k:
                del d[nums[i-k]]
        return False

• k값이 0이면 두 원소의 인덱스 차이가 없다는 의미입니다. 하지만 같은 두 값을 찾는 문제이므로 비교가 불가능합니다. 예외처리를 해줍니다.
• defaultdict으로 딕셔너리 d를 집합으로 선언합니다(키값이 할당되면서 0이 디폴트 값이 됩니다). 원소 값 : 인덱스의 키값쌍을 가집니다.
• nums를 탐색하다가 현재의 값이 딕셔너리에 존재한다면 True를 반환합니다.
  • 현재 값을 키, 인덱스값으로 d에 추가합니다.
  • 인덱스가 범위값인 k값 이상이 된다면 범위를 벗어나는 앞의 인덱스 i-k를 인덱스에서 지워줍니다.
• 반복문이 끝난다면 같은 값이 나온 적이 없다는 의미이므로 False를 반환합니다.

---

같은 값이 존재한다는 것을 알기위헤 내가 저장해두어야 할 값은 무엇이 가장 좋을지 고민했던 문제입니다.

1. 우선 k라는 범위가 주어졌으므로 인덱스가 저장되거나 k길이만큼 값을 저장해둘 자료구조가 필요합니다.
2. 같은 값이라는 것을 알기위해 값 자체도 저장이 되어야 합니다.

그래서 인덱스와 값을 저장할만한 좋은 객체는 딕셔너리였습니다.
어차피 인덱스는 값이 겹칠 일이 없고, nums의 원소값 또한 답이 나오기 전까지 겹칠 일이 없었으므로 정수:정수 쌍으로 키값을 결정했습니다.

이 외의 어려운 점은 없었고 결과도 무난하게 나왔습니다.