[LeetCode] 217. Contains Duplicate

371. Sum of Two Integers

LeetCode

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.

정수 배열 nums가 주어졌을 때, 배열 내에 어떤 값이 최소 두 번 이상 나타나면 true를 반환하고, 모든 요소가 고유하다면(중복이 없으면) false를 반환하세요.

 

Example

Input: nums = [1,2,3,1]
Output: true
Explanation: The element 1 occurs at the indices 0 and 3.

Input: nums = [1,2,3,4]
Output: false
Explanation: All elements are distinct.

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

---

 

1. 문제 요구사항 분석

배열에서 중복되는 값이 있으면 true, 없으면 false 문제

 

2. 접근 전략

😄  Set 사용 → 시간복잡도 : O(n) (배열 한 바퀴 돔)

참고) HashSet은 해시테이블을 사용하기 때문에 시간복잡도 O(1)

 

import java.util.*;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for (int num: nums) {
            if (set.contains(num)) {
                return true;
            } else {
                set.add(num);
            }
        }

        return false;
    }
}