268. Missing Number[Easy]

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?

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int sum = 0;
        for(int i=0; i<nums.size(); i++){
            sum += nums[i];
        }
        return (1 + nums.size()) * nums.size() / 2 - sum;
    }
};

Runtime: 36 ms, faster than 25.15% of C++ online submissions for Missing Number.
Memory Usage: 9.7 MB, less than 93.72% of C++ online submissions for Missing Number.

思路

• Miss Number = sub（数列求和, 数组加和）

优化

• 二进制异或操作，相同的为0，不同的为1，被保留下来。

    int missingNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < nums.size(); ++i){
            res ^= (i + 1) ^ nums[i];
        }
        return res;
    }

Runtime: 24 ms, faster than 98.06% of C++ online submissions for Missing Number.
Memory Usage: 9.8 MB, less than 52.19% of C++ online submissions for Missing Number.