268. Missing Number

Problem

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

https://leetcode.com/problems/missing-number/

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Test Cases

1 2	class Solution: def missingNumber(self, nums: List[int]) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([3,0,1], 2),
    ([0,1], 2),
    ([9,6,4,2,3,5,7,0,1], 8),
])
class Test:
    def test_solution(self, nums, expected):
        sol = Solution()
        assert sol.missingNumber(nums) == expected

Thoughts

把提供的数字全部累加起来，结果与 0 到 n 的累加结果 n * (n + 1) / 2 比较，差值就是所求的数。

时间复杂度 O(n)，空间复杂度 O(1)。

也不用全加完了再求差，可以对于第 i 个数字，计算 i 与该数字之差，把差值累加起来即可。

Code

solution.py

from typing import List


class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return sum(i - v for i, v in enumerate(nums, 1))

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。