[leetcode] 217 contains duplicate

217. 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.

 

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

 

해답

class Solution {
    public boolean containsDuplicate(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                } 
            }
        }
    return false;
    }
}

처음엔 별 생각없이.. (무식하게) 그대로 비교하는 식으로 짰다가 당연히 Time Limit Exceed가 떴다.

 

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

HashSet에 넣어 비교하는 방식으로 풀었더니 정상적으로 통과했다. 

 

참고로, HashSet.contain()의 복잡도는 O(1)이라고 한다.

https://stackoverflow.com/questions/25247854/what-is-the-time-complexity-performance-of-hashset-contains-in-java

What is the time complexity performance of HashSet.contains() in Java?