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

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

我们可以通过把数字本身和这些数字的平方相加来解Q2。

我们可以把问题简化为

k1 + k2 = x
k1^2 + k2^2 = y

其中x和y表示和低于期望值的程度。

代换给我们:

(x-k2)^2 + k2^2 = y

然后我们可以解出缺失的数。

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

下面是Dimitris Andreou链接的摘要。

记住i次幂的和，其中i=1 2 .. k。这就把问题简化为解方程组

A1 + A2 + ... + AK = B1

A12 + A22 + ... + AK2 = B2

...

a1k + a2k + ... + laas = bk

利用牛顿恒等式，知道bi就可以计算

c1 = a1 + a2 +ak

c2 = a1a2 + a1a3 +，+ ak-1ak

...

ck = a1a2 ..ak

如果你展开多项式(x-a1)…(x-ak)系数正好是c1，…， ck -见Viète的公式。由于每个多项式因子都是唯一的(多项式环是欧几里得域)，这意味着ai是唯一确定的，直到排列为止。

这就证明了记住幂就足以恢复数字。对于常数k，这是一个很好的方法。

However, when k is varying, the direct approach of computing c1,...,ck is prohibitely expensive, since e.g. ck is the product of all missing numbers, magnitude n!/(n-k)!. To overcome this, perform computations in Zq field, where q is a prime such that n <= q < 2n - it exists by Bertrand's postulate. The proof doesn't need to be changed, since the formulas still hold, and factorization of polynomials is still unique. You also need an algorithm for factorization over finite fields, for example the one by Berlekamp or Cantor-Zassenhaus.

常数k的高级伪代码:

计算给定数的i次幂 相减得到未知数字的i次幂的和。称这些和为bi。 利用牛顿恒等式从bi中计算系数;叫它们ci。c1 = b1;C2 = (c1b1 - b2)/2;详见维基百科的精确公式 因式分解多项式xk-c1xk-1 +…+ ck。 多项式的根是所需的数a1，…正义与发展党。

对于改变k，使用例如Miller-Rabin，找到质数n <= q < 2n，并对所有数字对q进行模数化简来执行步骤。

编辑:这个答案的前一个版本表明，可以使用特征2 (q=2^(log n))的有限域来代替Zq，其中q是素数。但事实并非如此，因为牛顿公式需要除以k以内的数。

我认为可以这样概括:

表示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而你只有两个方程可以解。

您可能需要澄清O(k)的含义。

这里有一个任意k的简单解:对于你的数字集中的每一个v，将2^v相加。最后，循环i从1到n，如果和2^i按位和为零，则i缺失。(或者在数字上，如果和的底除以2^i是偶数。或者模2^(i+1) < 2^i

容易,对吧?O(N)时间，O(1)存储，支持任意k。

除了你在计算一个巨大的数字，在真正的计算机上，每个数字都需要O(N)个空间。事实上，这个解和位向量是一样的。

所以你可以很聪明地计算和，平方和和和立方体的和…直到v^k的和，然后用复杂的数学方法提取结果。但这些都是很大的数字，这就引出了一个问题:我们谈论的是哪种抽象的运作模式?O(1)空间中有多少是合适的，以及需要多长时间才能将所需大小的数字相加?