LeetCode: 268. 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?
Credits: Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
自己的答案，13ms：
public class Solution { public int missingNumber(int[] nums) { if (nums == null || nums.length == 0) { return 0; } Arrays.sort(nums); int i = 0; for (i = 0; i < nums.length; i++) { if (nums[i] != i) { return i; } } return i; } }最快的答案，1ms：
public class Solution { public int missingNumber(int[] nums) { int sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; } return (nums.length * (nums.length + 1)) / 2 - sum; } }3 different ideas: XOR, SUM, Binary Search. Java code xor:
public int missingNumber(int[] nums) { //xor int res = nums.length; for(int i=0; i<nums.length; i++){ res ^= i; res ^= nums[i]; } return res; }求和：
public int missingNumber(int[] nums) { //sum int len = nums.length; int sum = (0+len)*(len+1)/2; for(int i=0; i<len; i++) sum-=nums[i]; return sum; }二分查找：
public int missingNumber(int[] nums) { //binary search Arrays.sort(nums); int left = 0, right = nums.length, mid= (left + right)/2; while(left<right){ mid = (left + right)/2; if(nums[mid]>mid) right = mid; else left = mid+1; } return left; }