这可能听起来很愚蠢，但是，在第一个问题中，你必须看到袋子里所有剩下的数字，然后用这个方程把它们加起来，找到缺失的数字。

既然你能看到所有的数字，那就找出少了的那个数字。当缺少两个数字时也是如此。我觉得很简单。当你看到袋子里剩下的数字时，用方程就没有意义了。

基于数字和的解决方案的问题是，它们没有考虑到存储和处理具有大指数的数字的成本……在实践中，为了使它适用于非常大的n，将使用大数库。我们可以分析这些算法的空间利用率。

我们可以分析sdcvvc和Dimitris Andreou算法的时间和空间复杂度。

储存:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

所以l_j \in \ (j log n)

所使用的总存储空间:\sum_{j=1}^k l_j \in \Theta(k^2 log n)

使用的空间:假设计算a^j需要ceil(log_2 j)时间，总时间:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

总使用时间:\Theta(kn log n)

如果这个时间和空间是令人满意的，您可以使用一个简单的递归 算法。让b !I是袋子里的第I个元素，n个之前的数字 移除次数，k是移除次数。在Haskell语法中…

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

使用的存储:O(k)用于列表，O(log(n))用于堆栈:O(k + log(n)) 该算法更直观，具有相同的时间复杂度，占用的空间更少。

正如@j_random_hacker所指出的，这与在O(n)个时间和O(1)个空间中寻找重复项非常相似，我的答案在这里也适用。

假设“袋子”由一个大小为N - k的基于1的数组a[]表示，我们可以在O(N)个时间和O(k)个额外空间内求解Qk。

首先，我们将数组A[]扩展k个元素，使它现在的大小为n，这是O(k)个额外空间。然后我们运行以下伪代码算法:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

第一个循环初始化k个额外的条目，使其与数组中的第一个条目相同(这只是我们知道数组中已经存在的一个方便的值——在这一步之后，大小为N-k的初始数组中缺失的任何条目在扩展数组中仍然缺失)。

第二个循环排列扩展数组，如果元素x至少出现一次，那么其中一个元素将位于位置A[x]。

注意，尽管它有一个嵌套循环，但它仍然在O(N)时间内运行——只有当有一个i使a [i] != i时才会发生交换，并且每次交换设置至少一个元素使a [i] == i，而以前不是这样的。这意味着交换的总数(因此while循环体的执行总数)最多为N-1。

第三个循环打印数组i中没有被值i占用的索引——这意味着i一定是缺失的。

我让一个4岁的孩子来解决这个问题。他把数字分类，然后开始数。这有一个O(厨房地板)的空间要求，它的工作就像许多球丢失一样简单。

我们可以用O(log n)来做Q1和Q2。

假设我们的存储芯片由n个试管阵列组成。试管中的数字x用x毫升化学液体表示。

假设我们的处理器是一束激光。当我们点燃激光时，它垂直穿过所有的管子。每次它通过化学液体，光度就降低1。在某毫升处通过光是O(1)的运算。

现在如果我们在试管的中间点上激光就会得到光度的输出

等于预先计算的值(当没有数字缺失时计算)，则缺失的数字大于n/2。 如果我们的输出更小，那么至少有一个小于n/2的数字缺失。我们也可以检查光度是否降低了1或2。如果它减少1，那么一个缺失数小于n/2，另一个大于n/2。如果它减2，那么两个数都小于n/2。

我们可以一次又一次地重复上述过程，缩小我们的问题域。在每一步中，我们将定义域缩小一半。最后我们可以得到结果。

值得一提的是并行算法(因为它们很有趣)，

sorting by some parallel algorithm, for example, parallel merge can be done in O(log^3 n) time. And then the missing number can be found by binary search in O(log n) time. Theoretically, if we have n processors then each process can check one of the inputs and set some flag that identifies the number(conveniently in an array). And in the next step each process can check each flag and finally output the number that is not flagged. The whole process will take O(1) time. It has additional O(n) space/memory requirement.

请注意，如上所述，上面提供的两个并行算法可能需要额外的空间。

我认为可以这样概括:

表示S, M为等差级数和乘法的初始值。

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

我应该考虑一个公式来计算这个，但这不是重点。无论如何，如果缺少一个数字，您已经提供了解决方案。但是，如果少了两个数字，让我们用S1和M1表示新的和和和总倍数，如下所示:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

因为你知道S1 M1 M和S，上面的方程是可以解出a和b，缺失的数字。

现在来看看遗漏的三个数字:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

现在未知量是3而你只有两个方程可以解。