[Easy] 217. Contains Duplicate

#문제 설명

Leetcode 217번 문제는 주어진 정수 배열에 중복된 숫자가 들어있는지 알아내는 문제이다. 배열에서 중복이 발생되면 true, 중복이 없다면 false를 return 하면 된다.

#문제 풀이

1. HashSet이용 풀이

Set에는 중복 데이터를 담을 수 없다는 특성이 있다. 이 특성을 활용하면 문제를 쉽게 풀수있다.

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        
        for(int i = 0; i < nums.length;i++){
            if(!set.add(nums[i])){
                return true;
            }
        }
        return false;
    }
}

먼저 HashSet를 만들고 array의 각 정수들을 HashSet에 담 다가, 만약 HashSet에 정수를 담을 수 없다면 (!set.add(nums[i])) true를 return해주면 된다. 이 알고리즘의 time complexity와 space complexity는 O(n)이다. 

2. Sorting (정렬) 이용 풀이

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

먼저 arrays.sort를 이용해 배열을 정렬 시키고 array 를 loop시켜주면서 index i의 값과 i+1의 값을 비교해주면 된다. 만약 index i와 i+1의 값이 같다면 true를 return시켜주면 된다. 이 알고리즘의 time complexity는 O(nlogn)이고 Space complexity는 constant (O(1))이다. 

3.  Brute Force 이용 풀이

이 풀이는 배열에 있는 모든 숫자를 한 번씩 비교한다. 그렇기 때문에 굉장히 느리고 비효율적이다.

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

Nested for loop을 사용해 모든 숫자를 비교할 수 있는 경우의 수를 커버 한다. 그렇기 때문에 space complexity는 constant space인 O(1)이지만 time complexity는 O(n^2) 으로 굉장히 느리다.