丢失的数字

难度: Easy

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

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：

输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：

n == nums.length
1 <= n <= 10⁴
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

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

Submission

运行时间: 27 ms

内存: 16.9 MB

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # nums.sort()
        # print(nums)
        # n = len(nums)
        # left, right = 0, n
        # while left<=right:
        #     mid = (right-left)//2+left
        #     if nums[mid]==mid:
        #         left=mid
        #     else:
        #         right=mid
        # print(left, right)

        # 方法一：根据和求解
        n = len(nums)
        s = (1+n)*n//2
        for i in range(n):
            s-=nums[i]
        return s

Explain

此题解采用了和的差值法。首先计算出0到n的和s，然后遍历数组nums，将数组中每个元素的值从s中减去。最后，s中剩余的值就是缺失的数字。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 计算0到n的和
        n = len(nums)
        s = (1 + n) * n // 2
        # 遍历数组，更新和
        for i in range(n):
            s -= nums[i]
        # 返回缺失的数字
        return s

Explore

和的差值法具有简单和高效的优点，时间复杂度为O(n)，空间复杂度为O(1)，不需要额外的存储空间。相比之下，使用哈希表虽然同样能在O(n)时间内解决问题，但需要O(n)的额外空间来存储元素。位运算方法也是一个有效的选择，但其逻辑可能不如和的差值法直观。因此，和的差值法在保证效率的同时，也尽可能地减少了内存的使用，适合解决此类问题。

在Python中，整数类型可以自动扩展为长整型，因此不必担心常规运算中的溢出问题。然而，在其他一些编程语言中（如Java、C++），确实需要注意整数溢出的问题。在这些语言中，可以通过使用数据类型如long来防止溢出，或者在每次加法操作后进行模运算来保持数值大小在安全范围内。

如果数组nums中包含重复的数字，和的差值法将不再有效。这种方法基于0到n的所有数字正好出现一次的前提。重复的数字会导致其他某个数字缺失，从而使得最终的计算结果不准确。因此，这种方法只适用于没有重复数字的情况。

是的，这种方法也能处理数组长度比预期短一位的情况，即缺失的是最大的数字n。由于初始的和是假设所有从0到n的数字都在的，如果数组长度短一位，那么缺失的数字必然是n，计算的差值方法能正确识别并返回n作为缺失的数字。