您还可以创建一个大小为last_element_in_the_existing_array + 1的布尔数组。

在for循环中，标记现有数组中存在的所有元素为true。

在另一个for循环中，打印包含false的元素的索引，即缺失的元素。

时间复杂度:O(last_element_in_the_existing_array)

空间复杂度:O(array.length)

我认为可以这样概括:

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

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

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

假设一个ArrayList对象(myList)被这些数字填充，其中x和y两个数字缺失。所以可能的解决方案是:

int k = 1;
        while (k < 100) {
            if (!myList.contains(k)) {
                System.out.println("Missing No:" + k);
            }
            k++;
        }

有一个通用的方法来解决这样的流问题。 我们的想法是使用一些随机化，希望将k个元素“分散”到独立的子问题中，在那里我们的原始算法为我们解决了问题。该技术用于稀疏信号重建等。

创建一个大小为u = k^2的数组a。 选取任意通用哈希函数h:{1，…，n} ->{1，…，u}。(如multiply-shift) 对于1中的每一个i，…， n增加a[h(i)] += i 对于输入流中的每个数字x，减去a[h(x)] -= x。

如果所有缺失的数字都已散列到不同的bucket中，则数组的非零元素现在将包含缺失的数字。

根据通用哈希函数的定义，特定对被发送到同一桶的概率小于1/u。由于大约有k^2/2对，我们有错误概率不超过k^2/2/u=1/2。也就是说，我们成功的概率至少是50%，如果我们增加u，我们的机会就会增加。

注意，这个算法占用k^2 logn位的空间(每个数组桶需要logn位)。这与@Dimitris Andreou的答案所需要的空间相匹配(特别是多项式因式分解的空间要求，它碰巧也是随机的。) 该算法每次更新的时间也是常数，而不是幂和情况下的时间k。

事实上，通过使用评论中描述的技巧，我们甚至可以比幂和法更有效。

要解决缺少2(和3)个数字的问题，您可以修改quickselect，它平均在O(n)内运行，如果分区是就地完成的，则使用恒定内存。

Partition the set with respect to a random pivot p into partitions l, which contain numbers smaller than the pivot, and r, which contain numbers greater than the pivot. Determine which partitions the 2 missing numbers are in by comparing the pivot value to the size of each partition (p - 1 - count(l) = count of missing numbers in l and n - count(r) - p = count of missing numbers in r) a) If each partition is missing one number, then use the difference of sums approach to find each missing number. (1 + 2 + ... + (p-1)) - sum(l) = missing #1 and ((p+1) + (p+2) ... + n) - sum(r) = missing #2 b) If one partition is missing both numbers and the partition is empty, then the missing numbers are either (p-1,p-2) or (p+1,p+2) depending on which partition is missing the numbers. If one partition is missing 2 numbers but is not empty, then recurse onto that partiton.

由于只缺少2个数字，该算法总是丢弃至少一个分区，因此保持了O(n)个快速选择的平均时间复杂度。类似地，当缺少3个数字时，该算法也会在每次传递中丢弃至少一个分区(因为当缺少2个数字时，最多只有1个分区包含多个缺少的数字)。然而，我不确定当添加更多缺失的数字时，性能会下降多少。

下面是一个不使用就地分区的实现，所以这个例子不满足空间要求，但它确实说明了算法的步骤:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Demo