# LeetCode Notes: Missing Number

## Question

Given an array `nums`

containing `n`

distinct numbers in the range `[0, n]`

, return *the only number in the range that is missing from the array.*

**Example 1:**

Input:nums = [3,0,1]

Output:2

Explanation**:** n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

**Example 2:**

Input:nums = [0,1]

Output:2

Explanation**:** n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

**Example 3:**

Input:nums = [9,6,4,2,3,5,7,0,1]

Output:8

Explanation**:** n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

**Example 4:**

Input:nums = [0]

Output:1

Explanation**:** n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

**Constraints:**

`n == nums.length`

- 1 <= n <= 10
^{4} `0 <= nums[i] <= n`

- All the numbers of
`nums`

are**unique**.

**Follow up:** Could you implement a solution using only `O(1)`

extra space complexity and `O(n)`

runtime complexity?

## Solution One

**Analysis:**

- Sort the numbers in the array first
- Traverse the array again to check whether the subscript and the value of the array can correspond, the uncorresponding number is the missing numebr
- Finally, consider the case where there is only
`0`

and the case where the missing number is the last one

**Code:**

```
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
const find = nums.sort((a,b) => a-b).findIndex((n,i) => {
return n !== i
})
return find !== -1 ? find : nums.length
};
```

## Solution Two

**Analysis:**

Traverse the numbers of `0 - n`

and check if they exist in the `nums`

array. The numbers not in the `nums`

array is the missing number.

**Code:**

```
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
for(let i = 0; i < nums.length + 1; i++){
if(!nums.includes(i)){
return i
}
}
};
```

## Solution Three

**Analysis:**

According to the above solution two, the performance of the `includes`

method of directly using the array is not very good. We switch to the `Set`

collection and use the `has`

of the `Set`

to find elements to improve query efficiency.

**Code:**

```
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
const set = new Set(nums)
for(let i = 0; i < nums.length + 1; i++){
if(!set.has(i)){
return i
}
}
};
```

## Comments