<p>

268. Missing Number

Total Accepted: 60895
Total Submissions: 147019
Difficulty: Medium

Given an array containing n distinct numbers taken from0, 1, 2, ..., n
, find the one that is missing from the array.
For example,Given nums =[0, 1, 3]
return2
.
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.
</p>

方法一

<code>

public class MissingNumber268 {
    public int missingNumber(int[] nums) {
        int absence=0;
        int temp[] = new int[nums.length+1];
        for(int i=0;i<nums.length;i++){
            temp[nums[i]] =1;
        }
        for(int i=0;i<temp.length;i++){
            if(temp[i]!=1){
                absence = i;
            }
        }
        return absence;
    }
    public static void main(String[] args){
        int nums[] = {0,1,3};
        MissingNumber268 mn = new MissingNumber268();
        System.out.println(mn.missingNumber(nums));
    }
}

</code>

方法二 （better）

<code>

public int missingNumber(int[] nums) {
        int absence = 0;
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            total += nums[i];
        }
        absence = (1 + nums.length) * nums.length / 2 - total;
        return absence;
    }

</code>