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?

Solution1: run time complexity is O(nlogn), constant space.

public class Solution {
    public int missingNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        Arrays.sort(nums);
        
        if (nums[0] != 0) {
            return 0; 
        }
        
        int i = 0;
        for (; i < nums.length - 1; i++) {
            if (nums[i + 1] - nums[i] != 1) {
                return nums[i] + 1;
            } 
        }
        
        return nums[i] + 1;
    }
}

Solution2: run time complexity is O(n), constant space.

The formula to calculate this sum:

 is  

Compute the sum of the given elements in the array. Use this sum to minus each element in the array, the difference will be the missing number.

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