[LeetCode] 217. Contains Duplicate

date

‣

slug

leetcode-217

author

status

Public

문제 링크

https://leetcode.com/problems/contains-duplicate/

문제

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

문제풀이

주어진 List안에 같은 값이 2개 이상 나오면 True

중복된게 하나도 없으면 (모두 1개만 나오면) False 입니다

2가지 방식이 있습니다.

List의 idx를 활용한 방법으로 범위가 아주 크지않을 때 사용가능합니다.

하지만 이 방법은 Constraints의 nums[i]가

범위이므로 메모리 초과가 납니다.

Dictionary 방식으로 범위가 아주 커도 사용가능합니다. 또한 접근이 이므로 아주빠른 해결이 가능합니다.

Linear Search 순회를 진행하면서 만나는 모든 num을 key로 하는 Dict에 +1값을 해주고 값이 2가 넘는 경우 바로 True를 리턴합니다. 모든 순회가 끝나는 경우 False를 리턴합니다.

파이썬 문제풀이 코드


class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        count_numbers = defaultdict(int)

        for num in nums:
            count_numbers[num] += 1

            if count_numbers[num] >= 2:
                return True

        return False

시간복잡도

제한사항

Constraints:

1 <= nums.length <= 10^5

10^9 <= nums[i] <= 10^9

예제 입력

Example 1:

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

Output: true

Explanation:

The element 1 occurs at the indices 0 and 3.

Example 2:

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

Output: false

Explanation:

All elements are distinct.

[LeetCode] 217. Contains Duplicate

문제 링크

문제

문제풀이

제한사항

예제 입력

예제 출력

알고리즘 분류