LeetCode:面试题：消失的数字——时间复杂度

**消失的数字**

**问题描述**

给定一个长度为 n 的整数数组 nums，包含从1 到 n 的每个数字一次。请找出该数组中缺失的数字。

**示例**

* 输入：nums = [1,2,3,4]
输出：5* 输入：nums = [1,2,4,6,3,7,8]
输出：5**解决方案**

我们可以使用哈希表来解决这个问题。首先，我们遍历数组，将每个数字添加到哈希表中。如果某个数字不在哈希表中，则它是缺失的。

class Solution:
 def findMissingNumber(self, nums):
 n = len(nums)
 num_set = set()
 # 将所有数字添加到集合中 for i in range(1, n +1):
 num_set.add(i)
 # 遍历数组，找出缺失的数字 for num in nums:
 if num not in num_set:
 return num # 如果没有找到缺失的数字，则缺失的数字是 n +1 return n +1

class Solution:
 def findMissingNumber(self, nums):
 n = len(nums)
 expected_sum = (n +1) * n //2 # 计算实际和 actual_sum = sum(nums)
 # 缺失的数字是实际和与预期和之差 return expected_sum - actual_sum