# 268. Missing Number

&#x20;[**268. Missing Number**](https://leetcode.com/problems/missing-number/solution/)

Given an array containing n distinct numbers taken from `0, 1, 2, ..., n`, find the one that is missing from the array.

**Example 1:**

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

**Example 2:**

```
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
```

***My Solutions:***

方法1：先sort，然后依次找到缺少的数字（当前数字和应有的index不相同的情况）

Time: O(nlgn); Space: O(1)

方法2：用HashSet储存所有数字，再找出缺少数字

Time: O(n); Space: O(n)

方法3：位运算，一个数字^自己是0，所以把所有数字和index XOR即可找到缺少数字

Time: O(n); Space: O(1)

Example：

| Index | 0 | 1 | 2 | 3 |
| ----- | - | - | - | - |
| Value | 0 | 1 | 3 | 4 |

missing=4∧(0∧0)∧(1∧1)∧(2∧3)∧(3∧4)=(4∧4)∧(0∧0)∧(1∧1)∧(3∧3)∧2=0∧0∧0∧0∧2=2

```
public class Solution {
    public int missingNumber(int[] nums) {
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            res ^= i;
            res ^= nums[i];
        }
        return res;
    }
}
```

方法4：数字在0。。。n之间，我们知道对于1。。n，总和是 n \* （n + 1）/ 2。所以把nums里所有数字相加，用公式之和减去数字相加之和，即是缺少的数字

Time: O(n); Space: O(1)
