Missing Number
Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
实现思路：
这道题蛮简单的，可以通过求和做差的方式来找出丢失的那一个数字。注意点：这道题肯定是丢失数据的，并且必须是存在0 的。 因此首先检测0是否在nums里，如果没有，则直接返回0。 如果实际的和与nums的和相等，则要返回一个比nums里最大值加一的数字即可。
python3代码实现：
class Solution:
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if 0 not in nums:
return 0
real_sum = 0
n = max(nums)
for i in range(n + 1):
real_sum += i
dis = real_sum - sum(nums)
if dis == 0:
return n + 1
else:
return dis