找出所缺的整數

題目

未排序的 n 個連續整數中少了一個，試著找到最快的方法算出少了哪一個。例如：3, 6, 9, 7, 8, 4，連續整數範圍為 3-9，少了 5。
How to find the missing integer in an array.

說明

這個題目我們直覺得可以使用 Hashtable 的方式來判斷哪些數字出現過，但是這樣題目就太簡單了，所以一般會再有一個額外的限制：空間複雜度為 O(1)。

所以在不使用 Hashtable 的情況下，我們只能用數學的方式去求解，此等差數列正好為梯形公式：(上底 + 下底) * 高 / 2。

接著利用公式的理論總和減去實際總和就是缺少的數字，以上面的例子為例：

1
2
3

(3 + 9) * 7 / 2 = 42
3 + 6 + 9 + 7 + 8 + 4 = 37
42 - 37 = 5

解法

static int Find(int[] array)
{
    int max = array[0];
    int min = array[0];
    int sum = 0;
    for (int i = 0; i < array.Length; ++i)
    {
        int n = array[i];
        max = Math.Max(n, max);
        min = Math.Min(n, min);
        sum += n;
    }
    return (max + min) * (max - min + 1) / 2 - sum;
}