您可以使用二分搜索来查找缺失(或连续)数字的间隔。运行时间应该是(num间隔)* log(平均间隔长度)* n。如果间隔不多，则很有用。

你可以通过阅读Muthukrishnan的几页-数据流算法:谜题1:寻找缺失的数字来找到它。它准确地显示了您正在寻找的泛化。也许这就是面试官读到的内容，也是他提出这些问题的原因。

还请参阅sdcvvc的直接相关答案，其中还包括伪代码(万岁!没有必要阅读那些棘手的数学公式:)(谢谢，干得好!)

// Size of numbers
def n=100;

// A list of numbers that is missing k numbers.
def list;

// A map
def map = [:];

// Populate the map so that it contains all numbers.
for(int index=0; index<n; index++)
{
  map[index+1] = index+1;  
}

// Get size of list that is missing k numbers.
def size = list.size();

// Remove all numbers, that exists in list, from the map.
for(int index=0; index<size; index++)
{
  map.remove(list.get(index));  
}

// Content of map is missing numbers
println("Missing numbers: " + map);

不确定，这是否是最有效的解决方案，但我会遍历所有条目，并使用bitset来记住，设置了哪些数字，然后测试0位。

我喜欢简单的解决方案，我甚至相信，它可能比计算和，或平方和等更快。

我已经阅读了所有30个答案，并找到了最简单的一个，即使用100位数组是最好的。但正如问题所说，我们不能使用大小为N的数组，我将使用O(1)空间复杂度和k次迭代，即O(NK)时间复杂度来解决这个问题。

为了让解释更简单，假设给了我从1到15的数字，其中两个少了，即9和14，但我不知道。让包看起来像这样:

,1,2,12,4,7,5,10,11,13,15,3,6 [8].

我们知道每个数字在内部都是以位的形式表示的。 对于16之前的数字，我们只需要4位。对于10^9之前的数字，我们将需要32位。但我们先关注4位然后再推广它。

现在，假设我们有从1到15的所有数字，那么在内部，我们会有这样的数字(如果我们把它们排序):

0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

但是现在少了两个数。所以我们的表示法看起来是这样的(为了理解，可以是任何顺序):

(2MSD|2LSD)
00|01
00|10
00|11
-----
01|00
01|01
01|10
01|11
-----
10|00
missing=(10|01) 
10|10
10|11
-----
11|00
11|01
missing=(11|10)
11|11

现在让我们创建一个大小为2的位数组，其中包含具有对应的两位最高位的数字的计数。即

= [__,__,__,__] 
   00,01,10,11

从左到右扫描袋子，填充上面的数组，使比特数组的每个bin都包含数字的计数。结果如下:

= [ 3, 4, 3, 3] 
   00,01,10,11

如果所有的数字都出现了，它看起来会是这样的:

= [ 3, 4, 4, 4] 
   00,01,10,11

因此，我们知道有两个数字缺失了:一个数字的最高两位有效位数是10，另一个数字的最高两位有效位数是11。现在再次扫描列表，并为下两位有效数字填写一个大小为2的位数组。这一次，只考虑前两位有效数字为10的元素。我们将有位数组为:

= [ 1, 0, 1, 1] 
   00,01,10,11

如果MSD=10的所有数字都存在，那么所有箱子中都有1个，但现在我们看到少了一个。因此，我们有MSD=10和LSD=01缺失的数字，即1001，即9。

类似地，如果我们再次扫描，但只考虑MSD=11的元素，我们得到MSD=11和LSD=10缺失，即1110，即14。

= [ 1, 0, 1, 1] 
   00,01,10,11

因此，我们可以在等量的空间中找到缺失的数字。我们可以推广到100 1000或10^9或任何一组数字。

参考资料:http://users.ece.utexas.edu/~adnan/afi-samples-new.pdf中的问题1.6

这里有一个解决方案，使用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; }
    }
}