Leetcode-268: Missing Number

[zeqing-guo]

Missing Number

Description

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?

My Solution

代码的run time是1 ms，代码的时间复杂度是O(n)，空间复杂度是O(1)。
代码如下所示：

public class Solution {
    public int missingNumber(int[] nums) {
        if (nums == null) {
            return 0;
        }

        long len = nums.length;
        long sumOfNums = 0;

        for (int num : nums) {
            sumOfNums += num;
        }

        long sumOfArray = len * (len + 1) >> 1;

        return (int) (sumOfArray - sumOfNums);
    }
}

Analysis

用int也行，测试用例不会溢出。