题目

给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

进阶:

  • 你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

解题思路

没啥好说的,missNum = n*(n+1)/2-sum(nums)

code

秒杀

  1. class Solution:
  2. def missingNumber(self, nums: List[int]) -> int:
  3. n = len(nums)
  4. S = n * (n+1) // 2
  5. return S-sum(nums)