219. 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.

 

 

풀이

 

 

배열 안의 두 인덱스의 숫자가 동일하고, 각 인덱스의 위치를 뺄셈으로 연산하여 절대값으로 변환한 뒤 , 그 값이 k보다 작다면 True를 리턴하고 찾지 못한다면 Fasle를 반환하는 문제이다.

 

1. 문자열로 저장해서 사용하는 방법 

딕셔너리에 문자열로 인덱스가 2,3,4 이 중복된다하면 '234'로 넣어서 문자열을 for문으로 순회하는방법으로 코드를 짰다.

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        dict = {}

        for i ,num in enumerate(nums):
            if num not in dict:
                dict[num] = str(i)
            else:
            	for j in dict[num]:
                if abs(i-j) <=k:
                    return True
                else:
                    dict[num]+=str(i)
            print(dict)
        return False

 

문제를 생각해보면 k보다 적어야 하기에 인덱스를 최신으로 갱신해주며 딕셔너리에 넣어주면 된다..

k보다 적어야하기에 계속해서 갱신해주면 순회하고있는 인덱스의 위치와 제일 가까운 위치가 된다.

간단한 방법인데 이때는 생각을 못했다..ㅋㅋ 시간복잡도도 위의 코드보다 더 좋다. 

 

2. 딕셔너리의 값을 최신 값으로 갱신해주기

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        dict = {}

        for i ,num in enumerate(nums):
            if num not in dict:
                dict[num] = i
            else:
                if i-dict[num] <=k:
                    return True
                else:
                    dict[num]=i
        return False
             

        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """

 

 

다른사람이 작성한 코드

    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        
        myDict={}
        
        for i in range(len(nums)):
            
            if nums[i] in myDict and abs(i-myDict[nums[i]])<=k:
                return True
            myDict[nums[i]]=i
        return False

 

위의 코드와 거의 똑같은 방법으로 풀었다.

 

def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
    d = defaultdict(int)
    s = set()
    for i,x in enumerate(nums):
        if x in s and i-d[x]<=k:
            return True
        d[x] = i
        s.add(x)
    return False

 

set을 사용해서 각 인덱스의 문자열이 나왔는지 유무를 파악하고 딕셔너리에 넣어두었던 값을 갱신하며 찾는 방법이다.