LeetCode-219 Contains Duplicate II 파이썬 풀이

Contains Duplicate II - LeetCode

문제

int형 배열 nums에서 값이 동일한 두 요소의 인덱스 차의 절대값이 k보다 작거나 같은 경우가 있다면 True를 반환하는 문제입니다.

풀이

1. nums를 순회하면서 i와 동일한 값을 가진 j가 존재하는지 찾습니다.

2. i 앞에 위치한 배열들은 이미 확인한 값들이기 때문에 i의 뒷부분만 조회하면 됩니다.

3. 만약 i와 동일한 값을 가진 j가 있다면 j인덱스를 구한 후 i - j의 절대값을 구한 후 k와 비교합니다.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
            for i in range(0,len(nums)-1):
                if nums[i] in nums[i+1:]:
                    j = nums.index(nums[i],i+1)
                    if abs(i-j) <= k:
                        return True
            return False

처음에 이렇게 풀었을 때 Time Linit Exceeded가 나길래, 어느 부분이 문제인가 했더니,

오류가 난 테스트 케이스가 nums가 굉장히 긴 경우였습니다. 혹시나 해서 nums의 중복이 없는 경우 바로 False를 반환하도록 추가 하였더니 성공하였습니다!!

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
            if len(set(nums)) == len(nums):
                return False
            for i in range(0,len(nums)-1):
                if nums[i] in nums[i+1:]:
                    j = nums.index(nums[i],i+1)
                    if abs(i-j) <= k:
                        return True
            return False