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
    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