268. Missing Number E

Q:

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?

A:
更改input array， 让 每个A[i] 放到其对应的i位置

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            int val = nums[i];
            if (val == i || val == nums.size())
                continue;
            // exchange i, and nums[i]
            int tmp = val;
            nums[i] = nums[val];
            nums[val] = tmp;
            --i;
        }
        for (int i = 0; i < nums.size(); ++i)
            if (nums[i] != i)
                return i;
        return nums.size();
    }
};

求和再相减

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

Mistakes: