题目描述：

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?

题目大意：

给定一个包含从0, 1, 2, ..., n, 选出的n个不同数字的数组，从中找出数组中缺失的那一个数。

例如，
给定 nums = [0, 1, 3] 返回2。

注意：

你的算法应该满足线性时间复杂度。你可以只使用常数空间复杂度完成此题吗？

解题思路：

解法I：等差数列前n项和 - 数组之和

Python代码：

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        return n * (n + 1) / 2 - sum(nums)

解法II：位运算（异或运算）

Python代码：

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = reduce(operator.xor, nums)
        b = reduce(operator.xor, range(len(nums) + 1))
        return a ^ b

本文链接：http://bookshadow.com/weblog/2015/08/24/leetcode-missing-number/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码