Title

the problem link

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

Example 1

Input: [3,0,1]
Output: 2
Example 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?

题目大意: 就是一个数组找缺失的那个数

Solution

首先想到可以用set，要hash的，其次也可以用总和减去每个数字，那差不就是嘛！但可能溢出，可以用Longlong，看int也能ac的。

看solution还可以用异或的，就是^操作符，所有数组元素和数组size异或结果就是所求结果

//cpp:

class Solution {
public:
	int missingNumber(vector<int>& nums) {
		unordered_set<int> uset;
		for (int i = 0; i < nums.size(); i++) {
			uset.insert(nums[i]);
		}
		for (int i = 0; i <= nums.size(); i++) {
			if (uset.find(i) == uset.end())
				return i;
		}
	}
};