본문 바로가기
알고리즘 문제/Leetcode

[leetcode][268] Missing Number

by 햄과함께 2021. 3. 3.
320x100

문제 : leetcode.com/problems/missing-number/


고유한 숫자 배열 nums가 주어질 때, 0~n 까지 수 중 누락된 수를 구하라.


누락된 수는 0~n까지 수들의 합에서 nums배열의 합을 뺀 값과 같다.

0~n까지 수들의 합은 등차수열의 합 공식으로 n(n+1)/2로 구할 수 있고, nums배열의 합은 배열을 한 번 탐색하면서 구할 수 있다.

 

시간복잡도는 O(n), 공간복잡도는 O(1).


소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/268.%20Missing%20Number.cpp

320x100

댓글