@@ -0,0 +1,1377 @@
+/**%0A * Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.%0A *%0A * For example,%0A * Given nums = %5B0, 1, 3%5D return 2.%0A *%0A * Note:%0A * Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?%0A *%0A *%0A * Tags: Array, Math, Bit Manipulation%0A * Similar Problems: (H) First Missing Positive, (M) Single Number, (H) Find the Duplicate Number%0A */%0Apublic class MissingNumber %7B%0A%0A    /**%0A     * Math%0A     * Considering that the n numbers are distinct, we can get the sum of the array%0A     * Then substract it from the sum of 0 ~ n%0A     */%0A    public int missingNumber1(int%5B%5D nums) %7B%0A        int res = nums.length * (nums.length + 1) / 2; // may overflow%0A        for (int n : nums) res -= n;%0A        return res;%0A    %7D%0A%0A    /**%0A     * avoid overflow%0A     */%0A    public int missingNumber2(int%5B%5D nums) %7B%0A        int res = 0;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            res += i + 1 - nums%5Bi%5D;%0A        %7D%0A        return res;%0A    %7D%0A%0A    /**%0A     * Bit Manipulation%0A     * xor all numbers in the array and from 0 to n, the result is the missing number%0A     */%0A    public int missingNumber3(int%5B%5D nums) %7B%0A        int xor = 0;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            xor = xor %5E nums%5Bi%5D %5E (i + 1);%0A        %7D%0A        return xor;%0A    %7D%0A%7D%0A

add 268 Missing Number