Leetcode #268 Missing Number
1225 ワード
Description
Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
Note Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Example
Given nums = [0, 1, 3] return 2.
Explain
連続する数であるため、総和は既知で、1つの数を少なくした後に1回と減らしてすぐ
Code
Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
Note
Example
Given nums = [0, 1, 3] return 2.
Explain
連続する数であるため、総和は既知で、1つの数を少なくした後に1回と減らしてすぐ
Code
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
total = len(nums) * (len(nums) + 1) / 2
nums_sum = 0
for i in nums:
nums_sum += i
return total - nums_sum