268. Missing Number

Question

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Solution 1

采用数学方法，从0到n的和减去从nums中的每个元素的和，得到的即是缺失的数字。
循环所有下标，每次在结果上加上下标的值，并减去下标对应的元素。最后需要再加上nums内元素数量+1的值。

Code

class Solution {
    public int missingNumber(int[] nums) {
        int sum = nums.length;
        for(int i = 0; i < nums.length; i++){
            sum -= nums[i];
            sum += i;
        }
        
        return sum;
    }
}

Solution 2

遍历，采用一个数组found[]记录是否访问过。
再次遍历，如果存在未访问过的位置，则返回下标。

Code

class Solution {
    public int missingNumber(int[] nums) {
        int res = 0;
        int[] found = new int[nums.length+1];
        for(int i = 0; i < nums.length; i++){
            found[nums[i]] = 1;
        }
        
        for(int i = 0; i <= nums.length; i++){
            if(found[i] == 0) res = i;
        }
        return res;
    }
}