谢谢你这个有趣的问题:

因为你让我想起了牛顿的工作，它真的可以解决这个问题

请参考牛顿恒等式

As变量的数量=方程的数量(必须为一致性)

我认为，对于这个问题，我们应该提高袋数的幂，以便创建不同的方程。

我不知道，但是，我相信如果有一个函数，比如f，我们要加上f(xi)

x1+x2+…+ xk = z1

x12 + x22 + ... + xk2 = z2

............

............

............

x1k + x2k + ... + xkk = XP

休息是一个不确定时间和空间复杂性的数学工作，但牛顿恒等式肯定会发挥重要作用。

我们不能用集合理论吗 .difference_update()或在这个问题方法中是否有线性代数的机会?

我相信我有一个O(k)时间和O(log(k)空间算法，前提是你有任意大整数的下限(x)和log2(x)函数:

你有一个k位的长整数(因此是log8(k)空间)，其中你加上x^2，其中x是你在袋子里找到的下一个数字:s=1^2+2^2+…这需要O(N)时间(这对面试官来说不是问题)。最后得到j= (log2(s))这是你要找的最大的数。然后s=s-j，重复上面的步骤:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

现在，对于2756位的整数，通常没有floor和log2函数，而是用于double。所以呢?简单地说，对于每2个字节(或1、3、4)，您可以使用这些函数来获得所需的数字，但这增加了O(N)因素的时间复杂度

这里有一个解决方案，使用k位额外的存储空间，没有任何聪明的技巧，只是简单。执行时间O (n)，额外空间O (k)。只是为了证明这个问题可以解决，而不需要先阅读解决方案或成为天才:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

我还没有检查数学，但我怀疑在计算Σ(n)的同时计算Σ(n^2)将提供足够的信息来得到两个缺失的数字，如果有三个，也要计算Σ(n^3)，等等。

我们假设它是一个从1到N的数组，它的元素是a1, a2， ....一个:

1+N=N+1;
2+N-1=N+1;

… 所以这个和是唯一的。我们可以从头到尾扫描数组来添加两个元素。如果和是N+1;好吧，否则它们就不见了。

for (I <= N/2) {
    temp = a[I] + a[n-I];
    if (temp != N+1) then
        Find the missing number or numbers
}

迭代这个循环，很容易就能得到答案。

这是个很简单的问题

void findMissing(){
    bool record[N] = {0};
    for(int i = 0; i < N; i++){
        record[bag[i]-1] = 1;
    }
    for(int i = 0; i < N; i++){
        if(!record[i]) cout << i+1 << endl;
    }
}

O(n)时间和空间复杂度