public class MissingNumber {
public int missingNumber(int[] nums) {
int n = nums.length;
int sum = n * (n + 1) / 2;
for(int num : nums){
sum = num;
}
return sum;
}
}
Java O(n) Solution with O(1) Space

@markfly Thank you. But there is a problem that the
sum
may be larger than the max integer. So the other one'sxor
solution is better.public int missingNumber(int[] nums) { int xor = 0, i; for(i = 0; i < nums.length; i++){ xor = xor ^ i ^ nums[i]; } return xor ^ i; }

@markfly
a ^ a = 0
, soa ^ a ^ b = b
. Assume this case:
nums
0 1 2 4 5
i
0 1 2 3 4
We miss3
.
After the loop,xor = 0 ^ 0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 4 ^ 4 ^ 5
.
Finallyxor = 3 ^ 5
. We want to returnxor ^ i
and at that timei
has become4 + 1 = 5
after the forloop. So we actually returnxor = 3 ^ 5 ^ 5 = 3
which is what we want. That make sense?

@JackQin so thanks for you reply,many of the clear,i want study with you ,can i get your twitter?where country from?

@markfly I am glad I have made it clear. I am just a beginner too. Sorry, I don't have twitter. We can discuss in Leetcode. :)

