268. Missing Number

2026-03-20

리트코드 268번 풀이

문제

풀이 1

아이디어

Set으로 등장한 숫자를 기록하고, 최댓값까지 순회하며 빠진 수를 찾는다. 모두 있다면 max + 1이 빠진 수다.

코드

function missingNumber(nums: number[]): number {
  let max = 0;
  const set = new Set();

  for (const num of nums) {
    set.add(num);
    max = Math.max(max, num);
  }

  for (let i = 0; i <= max; i++) {
    if (!set.has(i)) return i;
  }

  return max + 1;
}

시간 / 공간 복잡도

시간 복잡도: O(n)
공간 복잡도: O(n)

풀이 2

아이디어

0부터 max까지의 합(maxSum)과 실제 배열의 합(numsSum)의 차이로 빠진 수를 구한다. 단, 가장 큰 수가 빠진 경우(nums.length === max)는 따로 처리한다.

코드

function missingNumber(nums: number[]): number {
  const max = Math.max(...nums);
  const numsSum = nums.reduce((acc, cur) => acc + cur, 0);
  const maxSum = Math.floor((max * (max + 1)) / 2);

  return nums.length === max ? maxSum - numsSum : max + 1;
}

시간 / 공간 복잡도

시간 복잡도: O(n)
공간 복잡도: O(1)

Back