# Missing Number

### 描述​

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

For example,

Given nums = [0, 1, 3] return 2.

Note:

Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

### 解法 1​

// Missing Number// Time Complexity: O(n), Space Complexity: O(1)public class Solution {    public int missingNumber(int[] nums) {        int sum = 0;        for (int x : nums) {            sum += x;        }        final int n = nums.length;        final int sumExpected = (n * (n + 1)) / 2;        return sumExpected - sum;    }}

### 解法 2​

// Missing Number// Time Complexity: O(n), Space Complexity: O(1)public class Solution {    public int missingNumber(int[] nums) {        int result = 0;        for (int i = 0; i < nums.length; ++i) {            result ^= (i+1) ^ nums[i];        }        return result;    }}

### 解法 3​

// Missing Number// Time Complexity: O(nlogn), Space Complexity: O(1)public class Solution {    public int missingNumber(int[] nums) {        Arrays.sort(nums);        int begin = 0;        int end = nums.length;        while (begin != end) {            final int mid = begin + (end - begin) / 2;            if (mid < nums[mid]) end = mid;            else begin = mid + 1;        }        return end;    }}