[LeetCode] 217. Contains Duplicate

Problem

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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

---

Solution

Logic

1. 배열의 모든 요소를 Set에 저장한다.

2. Set의 크기와 배열의 크기가 같으면 true를 반환하고, 그렇지 않으면 false를 반환한다.

   Code

   class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        return set.size() != nums.length;
    }
   }
   

   Time Complexity

   • 배열 nums의 크기를 n이라 가정할 때, 코드의 수행 시간을 좌우하는 것은 for반복문의 n번 계산 수행 시간이다. 따라서 본 솔루션은 O(n)의 시간 복잡도를 가진다.