leetcode
268.?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?
分析：題目要求在線性時間復(fù)雜度，常量級額外空間完成戈稿，這就意味著無法通過排序解題，應(yīng)用暴力求解需了，分別判斷每個數(shù)字是否確實般甲，時間超時肋乍，筆者想了一個很低端的辦法敷存，就是把給定的數(shù)組進行加和，然后利用（首項+末項）*項數(shù)/2計算給定的n的總和觅闽，將總和減去給定的每一項帝雇，最后剩下的數(shù)字即為所求
class Solution:
? ? def missingNumber(self, nums):
? ? ? ? """
? ? ? ? :type nums: List[int]
? ? ? ? :rtype: int
? ? ? ? """
#計算給定n值得總和
? ? ? ? sums = (1+len(nums))*len(nums)//2? ??
? ? ? ? for i in nums:
? ? ? ? ? ? sums -= i
? ? ? ? return sums
