268. Missing Number

方法一

思路

利用[0, n]的区间内和是(0 + n) * (n + 1) / 2
因为缺少一个数，那么和减去数组中的所有数字就是剩下的

方法二

思路

利用a ^ b ^b = a
由于nums[i] = i因此最后剩下的就是缺少的数字
例如
k = k ^ i ^ nums[i]
i = {0,1,2,3}
nums = {0,2,3,4}
k = 4
最后只剩下1没有消除
因此缺少1

与改题目类似的还有136. Single Number
a ^ b ^b = a

代码

1
2
3
4
5
6
7
8
9
10
11
public int missingNumber(int[] nums) {
	int k = nums.length;
	for (int i = 0; i < nums.length; i++) {
		// 可能会溢出
		// k = k ^ i ^ nums[i];
		k ^= i;
		k ^= nums[i];
	}
	System.out.println(k);
	return k;
}