难度: Hard
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
输入: [1]
输出: [2,3]
示例 2:
输入: [2,3]
输出: [1,4]
提示：
nums.length <= 30000
Submission
运行时间: 33 ms
内存: 20.0 MB
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
n = len(nums) + 2
missing_total = (1 + n) * n / 2 - sum(nums)
limit = missing_total // 2
current_sum = 0
for i in nums:
if i <= limit:
current_sum += i
missing = (1 + limit) * limit / 2 - current_sum
return [int(missing), int(missing_total - missing)]
Explain
该题解采用了数学方法来找出缺失的两个数字。首先，计算从1到N的所有数字的理论和，然后从中减去数组中的实际和，得到两个缺失数字的总和。接下来，以这个总和的一半作为界限，将小于或等于这个界限的所有数字的和计算出来。这样可以找出小于或等于界限的那个缺失数字，进而通过总和减去这个数字得到第二个缺失数字。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition of the solution class
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
n = len(nums) + 2 # Total numbers including the missing ones
# Calculate the sum of all numbers from 1 to n
missing_total = (1 + n) * n / 2 - sum(nums)
limit = missing_total // 2 # Divide the total missing sum by two
current_sum = 0
# Sum numbers in the array that are less than or equal to the limit
for i in nums:
if i <= limit:
current_sum += i
# Calculate the missing number that is less than or equal to the limit
missing = (1 + limit) * limit / 2 - current_sum
# The other missing number is the total missing sum minus the first missing number
return [int(missing), int(missing_total - missing)]
Explore
计算从1到N的所有数字的理论和和数组中的实际和，目的是确定两个缺失数字的总和。这是因为从1到N的和是一个固定的数值，可以通过公式计算得出。而数组中的实际和是当前数组中所有数字的总和。两者的差值即为缺失的两个数字的和。这个差值是找出缺失数字的关键第一步。
使用`missing_total // 2`作为界限来区分两个缺失数字基于一个假设：缺失的两个数字分别位于1到limit和limit+1到N的范围内。这个方法通常有效，因为即使两个缺失数字的和接近但不等于N，它们也会被分到两个不同的区间。然而，如果两个缺失的数字恰好相等并且等于`missing_total // 2`，这种方法可能会失效，因为这样的数字将不会被正确地区分到两个不同的区间。
这种方法假设数组中不存在重复数字，且确实缺少两个数字。如果数组中存在重复的数字，则计算的实际和不再只是简单地缺少两个数字的和，这可能导致计算错误。在存在重复数字的情况下，这种基于和的方法可能不再适用，需要采用其他方法（如位运算或哈希表）来正确识别缺失的数字。