217. 중복 포함 - Leetcode Easy

문제 설명

정수 배열 nums가 주어지면 값이 배열에 두 번 이상 나타나면 true를 반환하고 모든 요소가 고유하면 false를 반환합니다.

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

Input: nums = [1,2,3,4]
Output: false

접근법 1(무차별 대입)

매번 배열에서 항목을 선택합시다. 이제 남은 배열을 살펴보고 동일한 값을 가진 다른 항목이 존재하는지 살펴보겠습니다. 존재하는 경우 true를 반환합니다. 그렇지 않으면 거짓입니다.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i] == nums[j]:
                    return True
        return False

시간 복잡도: O(n^2) - 중첩된 for 루프 때문입니다.
공간 복잡성: O(1)

접근법 2

입력 배열을 정렬하면 모든 중복 요소가 나란히 재정렬됩니다. 배열을 순회하면서 인접 요소가 동일한지 계속 확인할 수 있습니다. 그러한 쌍을 찾으면 true를 반환할 수 있습니다.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                return True

        return False

시간 복잡도: O(n log n) - 정렬 때문에.
공간 복잡성: O(1)

접근법 3

배열을 반복하면서 각 항목을 해시셋에 계속 추가해 봅시다. 그리고 추가하기 전에 해당 항목이 해당 해시셋에 이미 있는지 확인하십시오. 이 검사 작업은 해시셋이기 때문에 O(1) 시간이 걸립니다. 그러한 요소를 찾으면 true를 반환할 수 있습니다.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hashSet = set()
        for n in nums:
            if n in hashSet:
                return True
            else:
                hashSet.add(n)

        return False

시간 복잡도: O(n) - 단 하나의 for 루프.
공간 복잡성: O(n) - 추가 해시셋의 경우.

결론

다른 접근 방식을 놓친 경우 알려주십시오.

더 많은 설명을 위해 나를 따르십시오.
연결합시다: Showwcase