268. Missing Number

문제

https://leetcode.com/problems/missing-number/

풀이

1. 처음 풀이 (Map 또는 Set 이용)

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int n : nums) {
            set.add(n);
        }

        for(int i = 0; i <= nums.length; i++) {
            if(!set.contains(i)) {
                return i;
            }
        }
        return -1;
    }
}

• 특정 원소가 존재하는지 파악해야함
  • HashSet.contains()나 HashMap.contains()의 시간복잡도는 O(1)
  • 값이 한번씩만 등장하기 때문에 Set, 정렬이나 삽입순서가 중요하지 않기 때문에 HashSet 사용
• nums containing n distinct numbers in the range [0, n]이기 때문에 마지막 return에는 도달 불가
• Set이나 Map을 이용하면 시간복잡도 O(N)을 만족하지만, 공간복잡도 O(1)으로 풀수는 없다.

2. 다른 풀이 (합 이용, 공간복잡도 O(1))

class Solution {
    public int missingNumber(int[] nums) {
    	int n = nums.length;
        int totalSum = (n * (n+1)) / 2;
        int actualSum = 0;

        for(int i = 0; i < nums.length; i++) {
            actualSum += nums[i];
        }
        
        return totalSum - actualSum;
    }
}

• 0부터 n까지의 합을 구한 뒤, 실제 배열의 합을 빼면 missing number를 찾을 수 있다.