Description：

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?

Credits:

Special thanks to  for adding this problem and creating all test cases.

查找0~n缺失的数。

首先可以先对数组排序，然后线性查找。时间复杂度是O(nlogn + n)，不满足题意但是也可以AC。

 

 

public class Solution {    public int missingNumber(int[] nums) {                Arrays.sort(nums);                if(nums[0] != 0) {            return 0;        }                for(int i=0; i

如果要求是线性时间复杂度可以以空间换时间。设置一个辅助数组来记录存在的数。时间复杂度是O(n)，空间复杂度是O(n)

 

public class Solution {    public int missingNumber(int[] nums) {                int[] count = new int[nums.length + 1];                Arrays.fill(count, 0);        //0 0                for(int i=0; i

以上两种方法并不完全满足题目要求，题目的最终要求是在线性时间复杂度和常数空间复杂度下完成。可以利用等差数列的求和公式求出0~n的和，然后逐一减去nums中的数剩下的也就是缺失的那个数了。时间复杂度O(n)，空间复杂度O(1)。

 

public class Solution {    public int missingNumber(int[] nums) {                int n = nums.length;                int sum = (1 + n) * n / 2;                for(int i=0; i