leetcode217. Contains Duplicate

217. Contains Duplicate

문제출저

정수형 배열이 주어질때, 중복된 값이 있는지 찾는다.
배열 중에서 두번이상 나온 값이 있으면 true값을 리턴해주고, 없으면 false를 리톤해준다.

예제1

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

예제1

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

나의 풀이

Set을 이용해서 풀었다.
Set에 현재 배열에서 참조하는 값이 이미 존재한다면, 중복된 값이라는 의미이므로 true를 리턴해주었다.
HashSet에서 Contrains는 O(1) 시간에 수행되므로,
n개의 배열이 주어진다면, 답을 얻는데 걸리는 시간은 O(n)이 소요될 것이다.

     public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                return true;
            }
            set.add(num);
        }
        return false;
    }

Leetcode Article

참조

시간복잡도를 고려했을땐, Leetcode Article에 나와있는 방법중 내가 풀었던 방식이 제일 빠르게 수행되는것 같다. 다만 HashSet을 이용한 별도의 공간이 요구된다. 만약 n개의 원소를 다 set에 담게되는 경우 O(n)만큼의 공간복잡도가 나온다.