问题描述:

给出从0到n的n+1个数字中的n个数，找到缺失的那个数字
注意：给定的数组并不一定是有序的数组

Paste_Image.png

代码示例一：时间复杂度较高,因为先对数组进行了排序

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        n = len(nums)
        if nums[0] != 0: return 0
        for i in range(1,n):
            if nums[i] != nums[i-1] + 1:
                return i
        return n

代码示例二：根据数学知识进行求解，0,1,2,,,n等差数列求和 - 数组的总和 即为缺失的那个数字

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        sum_n = n*(n+1)/2    #等差数列求和
        return sum_n - sum(nums)