面试题 17.19. 消失的两个数字 : 简单数学运用题

​

题目描述

这是 LeetCode 上的 面试题 17.19. 消失的两个数字 ，难度为 困难。

Tag : 「数学」

给定一个数组，包含从 ​

​1​

​​ 到 ​

​N​

​​ 所有的整数，但其中缺了两个数字。你能在 时间内只用

以任意顺序返回这两个数字均可。

示例 1:

输入: [1]

输出: [2,3]      

示例 2:

输入: [2,3]

输出: [1,4]      

提示：

数学

根据题意，给定 ​

​nums​

​​ 的长度为 且缺失了两个数，所有的 加上缺失数字组成连续排列长度为 。

根据等差数量求和公式可知，补齐后的排列总和为 ，补全后的理论总和与实际总和之间的差值

根据补全后数值各不相同可知，两者必不可能同时位于 的同一侧（偏大、偏小或数值重复），因此我们可以计算 范围内的理论总和与实际总和之间的差值来确定其一（将问题转换为求解缺失一值），再结合缺失两值之和

Java 代码：

class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length + 2, cur = n * (1 + n) / 2;
        for (int x : nums) cur -= x;
        int sum = cur, t = cur / 2;
        cur = t * (1 + t) / 2;
        for (int x : nums) {
            if (x <= t) cur -= x;
        }
        return new int[]{cur, sum - cur};
    }
}      

TypeScript 代码：

function missingTwo(nums: number[]): number[] {
    let n = nums.length + 2, cur = Math.floor(n * (1 + n) / 2)
    for (let x of nums) cur -= x
    let sum = cur, t = Math.floor(cur / 2)
    cur = Math.floor(t * (1 + t) / 2)
    for (let x of nums) {
        if (x <= t) cur -= x
    }
    return      

Python 代码：

class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        n = len(nums) + 2
        cur = n * (1 + n) // 2 - sum(nums)
        tot, t = cur, cur // 2
        cur = t * (1 + t) // 2 - sum([x for x in nums if x <= t])
        return      

• 时间复杂度：
• 空间复杂度：

最后

这是我们「刷穿 LeetCode」系列文章的第 ​

​No.面试题 17.19​

​ 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。