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?

这道题需要注意的是array中的数并不一定按顺序排列。 注意到这里只有一个missing number。 若没有missing，则0, 1, ..., n，数组长度应为n+1，而少了一个数后，数组长度恰好为n。 可以将0到n求和，然后将array中的数减去，最后剩余的即是missing number。

public class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int sum = n*(n+1)/2;
        for(int num: nums) {
            sum -= num;
        }
        return sum;
    }
}