可能重複：
Find two missing numbers包含n-2個整數的數組1到n，O（n）算法用O（1）額外空間查找缺少的2個數字？
我一直在想了一會兒，似乎無法得到一個答案......所以在N-2獨有的整數數組給出了除了陣列使用的空間外，從1到n和O（1）空間的範圍。你怎麼能找到在O（n）時間內在數組中缺少的從1到n的兩個整數？
因此，例如，a = [4,3,1,6]和O（1）額外空間 如何在O（n）時間內找到2，5？
這是一個想法：只要保持一些統計數據，爲您提供有關缺少數字的信息。例如，如果你計算出所有你的號碼爲S，則總和：
(1+2+..+N) - S = a+b
其中A和B是你丟失號碼。在你的榜樣，您可以：
1+2+3+4+5+6 - 4+3+1+6 = 7 = a+b
然後，您可以也做同樣的，例如，用於乘法並獲得：
(1*2*..*N)/S = a*b
你的情況：
(1*2*3*4*5*6)/72 = 10 = a*b
所以答案是2和5.
基本上有很多統計資料可以用這種方式...
the想法很有趣，但你怎麼知道哪些數字是缺失的，比如說a + b = 7。（a，b）可能是（1,6）或（3,4）？ – Krypton
@Krypton因爲你也有產品給你第二個約束，所以a * b = 10，並且因爲1 * 6 = 6和3 * 4 = 12答案必須是2 * 5 ... – Bitwise
1 * 2 * 3 * .... * n不是'O（1）'空間，也不是'O（N）'時間。由於：1 * 2 * ... * N = N！'表示'N！'，您將需要'O（1）'空間和時間對於重複乘法失敗（N * log（N））位。因此，即使忽略整數的「O（log（N））」位（通常是假設），也不能忽略「N」因子 – amit
它已被回答多次：http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe http：// stackoverflow.com/questions/10218791/find-two-missing-numbers http://stackoverflow.com/questions/555744/algorithm-to-find-two-repeated-numbers-in-an-array-without-sorting –