> For the complete documentation index, see [llms.txt](https://hannahpun.gitbook.io/leetcode-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hannahpun.gitbook.io/leetcode-note/array/268-missing-number..md).

# # 268 Missing Number.

換個想法快超級多，可以先從總和下去想

[LeetCode](https://leetcode.com/problems/missing-number/)

```
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, 
find the one that is missing from the array.
input: 一串數字陣列
output: 找出消失的那個
```

```
Example 1:

Input: [3,0,1]
Output: 2
Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. 
Could you implement it using only constant extra space complexity?

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    
};
```

### 怎麼解

第一個想法是先排序後前後比對，但這樣會用到  時間複雜度 Big O (n²)，\
其實可以先算出總長度，再減掉 input 就可以找到消失那個值！以 \[3, 0, 1] 來說，

* 我一開始就會知道 length  = 3，所以總和是 (1+3)\*3/2 = 6
* 6 - 3 - 0 - 1 = 2，所以是 2 消失了 

```
var missingNumber = function(nums) {
  let len = nums.length
  let correctSum = (1 + len)*len/2
  let currentSum = nums.reduce((a, b) => a + b);
  return correctSum - currentSum;
};
```