# 268 Missing Number.

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

LeetCode

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;
};