APPROACH: BINARY SEARCH

其实二分搜索很多地方都又变种，有时候不一定是要「找到目标」(nums[mid] == value那种)，比如这个，思路这样的：

1. 排序后，nums[mid] 如果等于mid，说明缺少的那个数在mid的右边，那么left = mid + 1。如：
   0123467
2. 如果nums[mid]>mid,说明缺少的那个数在mid左边，那么right = mid;

注意终止条件，left<right，而不是标准二分的<=。因为left == right 的情形就已经是找到了。

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;
}

APPROACH: SUM

我想到了这个方法。

        if (nums == null || nums.length == 0) return -1;
        int total = 0;
        for (int i : nums) {
            total += i;
        }
        return (1 + nums.length) * (nums.length) / 2 - total;

//or：
    int len = nums.length;
    int sum = (0+len)*(len+1)/2;
    for(int i=0; i<len; i++)
        sum-=nums[i];
    return sum;

APPROACH : XOR

我又没想到。明明跟SINGLE NUMBER和389那么像。。还是用得少。注意0异或任何数都等于0。

        //0异或任何数都等于0
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i] ^ i;
        }
        return res ^ (nums.length );