难度: Easy
Submission
运行时间: 22 ms
内存: 16.1 MB
from typing import List
class Solution:
def missingNumber(self, arr: List[int]) -> int:
n = len(arr)
# 计算原始数组的长度
original_length = n + 1
# 计算原始数组的总和
total_sum = (arr[0] + arr[n-1]) * original_length // 2
# 计算给定数组的总和
current_sum = sum(arr)
# 计算被删除的数
missing_number = total_sum - current_sum
return missing_number
Explain
这个题解利用了等差数列的性质。首先，计算原始等差数列（假设没有数字缺失的情况下）的长度，这是给定数组长度加一。接着，使用等差数列的首项和末项计算原始数组的理论总和。然后，计算实际给定数组的总和。原始的数组总和减去当前的数组总和，得到的差值就是被删除的那个数字。
时间复杂度: O(n)
空间复杂度: O(1)
from typing import List
class Solution:
def missingNumber(self, arr: List[int]) -> int:
n = len(arr) # 数组的长度
original_length = n + 1 # 原始等差数列的长度
# 计算原始等差数列的总和，利用等差数列的求和公式 (首项 + 末项) * 项数 / 2
total_sum = (arr[0] + arr[n-1]) * original_length // 2
# 计算给定数组的元素总和
current_sum = sum(arr)
# 计算缺失的数字，即原始总和与当前总和的差
missing_number = total_sum - current_sum
return missing_number # 返回缺失的数字
Explore
题解中使用的方法确保了即使缺失数字位于等差数列的首位或末位，使用首项和末项计算的等差数列总和依然正确。这是因为无论缺失的数字在哪里，等差数列的首项和末项（完整数列的首项和末项）是不变的。通过计算这个范围内的理论总和，然后与实际总和比较，可以准确地找出缺失的数字。
题解的方法依赖于数组是按照等差数列顺序排列的。如果数组的顺序被打乱，直接使用题解中的方法则不适用，因为它依赖于使用数组的首尾元素来确定完整数列的首项和末项。如果顺序被打乱，需要先对数组进行排序，然后再应用相同的逻辑来找出缺失的数字。
确实，这种方法依赖于数组至少有两个元素来确定等差数列的首项和末项。如果数组只有一个元素，无法直接计算出等差数列的末项，因此也就无法使用等差数列的总和公式。在这种情况下，如果已知等差数列的公差，可以利用单个元素推算出另一个元素，从而找出缺失的数字。如果数组为空，则无法应用此方法，因为没有任何信息来推断缺失的数字或等差数列的性质。
在大部分情况下，这种方法是准确的，因为它基于等差数列的数学性质。然而，如果输入数据中存在错误，例如数组中的元素不符合等差数列的规则（不是真正的等差数列），或者有多于一个数字缺失，这种方法将无法正确工作。此外，如果数组的数据类型或计算过程中导致整数溢出，也可能出现错误。