題意

給一個大小為n的數組，里面的元素為[0, n]中缺了一個數字，求缺的那個數字。

要求：

思路

算法1

如果數組包含[1, n]那么它的和為n(n+1)2$/frac{n(n+1)}{2}$。那么我們現在只需要對數組求和，兩個相減，得到的就是缺失的那個數字了。

算法2

利用異或。

我們知道^為：1 ^ 1 = 0, 0 ^ 1 = 1。

那么，就可以得到這樣兩個結論：

然后，對于這道題，我們可以另x1 = 0 ^ 1 ^ 2 ^ ....^ n，x2 = a[0] ^ a[0] ^...a[n - 1]

最后，我們用x1 ^ x2，可以知道：如果一個數y在a[]中出現過，假設為ak$a_k$，那么y ^ a[k] = 0。

基于這個思想，假設我們沒有出現的數是z，那么我們最后x1 ^ x2的結果即為：0 ^ z = z。

代碼