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

下面是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以内的数。

我使用Java 8和Java 8之前的版本编写代码。 它使用一个公式:(N*(N+1))/2作为所有数字的和。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

   /**
 * 
 * 
 * @author pradeep
 * 
 *         Answer : SumOfAllNumbers-SumOfPresentNumbers=Missing Number;
 * 
 *         To GET SumOfAllNumbers : Get the highest number (N) by checking the
 *         length. and use the formula (N*(N+1))/2
 * 
 *         To GET SumOfPresentNumbers: iterate and add it
 * 
 * 
 */
public class FindMissingNumber {
    /**
     * Before Java 8
     * 
     * @param numbers
     * @return
     */
    public static int missingNumber(List<Integer> numbers) {
        int sumOfPresentNumbers = 0;
        for (Integer integer : numbers) {
            sumOfPresentNumbers = sumOfPresentNumbers + integer;
        }
        int n = numbers.size();
        int sumOfAllNumbers = (n * (n + 1)) / 2;
        return sumOfAllNumbers - sumOfPresentNumbers;
    }
    /**
     * Using Java 8 . mapToInt & sum using streams.
     * 
     * @param numbers
     * @return
     */
    public static int missingNumberJava8(List<Integer> numbers) {
        int sumOfPresentNumbers = numbers.stream().mapToInt(i -> i).sum();
        int n = numbers.size();
        int sumOfAllNumbers = (n * (n + 1)) / 2;
        return sumOfAllNumbers - sumOfPresentNumbers;
    }
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list = Arrays.asList(0, 1, 2, 4);
        System.out.println("Missing number is :  " + missingNumber(list));
        System.out.println("Missing number using Java 8 is : " + missingNumberJava8(list));
    }
}*

一个可能的解决方案:

public class MissingNumber {
    public static void main(String[] args) {
        // 0-20
        int [] a = {1,4,3,6,7,9,8,11,10,12,15,18,14};
        printMissingNumbers(a,20);
    }

    public static void printMissingNumbers(int [] a, int upperLimit){
        int b [] = new int[upperLimit];
        for(int i = 0; i < a.length; i++){
            b[a[i]] = 1;
        }
        for(int k = 0; k < upperLimit; k++){
            if(b[k] == 0)
                System.out.println(k);
        }
    }
}

// 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);

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