面試題 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 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。