# C#LeetCode刷题之#268-缺失数字（Missing Number）

Given an array containing n distinct numbers taken from `0, 1, 2, ..., n`, find the one that is missing from the array.

Input: [3,0,1]

Output: 2

Input: [9,6,4,2,3,5,7,0,1]

Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

```public class Program {

public static void Main(string[] args) {
int[] nums = null;

nums = new int[] { 9, 6, 4, 2, 3, 5, 7, 0, 1 };
var res = MissingNumber(nums);
Console.WriteLine(res);

res = MissingNumber2(nums);
Console.WriteLine(res);

}

private static int MissingNumber(int[] nums) {
//求和法
if(!nums.Contains(0)) return 0;
var sum = 0;
foreach(var num in nums) {
sum += num;
}
int max = nums.Length;
return (1 + max) * max / 2 - sum;
}

private static int MissingNumber2(int[] nums) {
//异或法
//异或满足交换律，我们有以下公式
//A ^ B = B ^ A
//(A ^ B) ^ C = A ^ (B ^ C)
//A ^ C ^ B ^ A ^ C = A ^ A ^ C ^ C ^ B = B
//对于数组 [2, 3, 4, 0]
//res初始值为 0
//异或 0 ^ (2 ^ 1) ^ (3 ^ 2) ^ (4 ^ 3) ^ (0 ^ 4)
//= (0 ^ 0) ^ (1) ^ (2 ^ 2) ^ (3 ^ 3) ^ (4 ^ 4) = 1
int res = 0;
for(int i = 0; i < nums.Length; i++)
res ^= nums[i] ^ (i + 1);
return res;
}

}```

```8
8```