題目：
給定一個由 0, 1, 2, ..., n 組成的陣列 nums，其中恰好缺少了一個數字。我們需要找到這個缺少的數字。

範例：

輸入: nums = [3, 0, 1]
輸出: 2

輸入: nums = [0, 1]
輸出: 2

輸入: nums = [9,6,4,2,3,5,7,0,1]
輸出: 8

解題思路

這道題本質上是處理數列中一個數字的缺少問題，有好幾種解法。

解法1：排序法

最直覺的方式是先排序後再找出那個缺少的數字，

實作：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        if (nums.size() == 1)
            return nums[0] == 0 ? 1 : 0;
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] - nums[i-1] == 2)
                return nums[i]-1;
        }
        return nums[0] == 0 ? nums.size() : 0;
    }
};

解法2：數學法

利用等差數列和公式算出總和，再減掉陣列的總和就是那缺少的數字，跟前一個方法比較，少了排序。如果對 accumulate (C++20) 函式熟悉的話就可以直接使用，少寫一些code。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int totalSum = nums.size() * (1+nums.size()) / 2;

        //int arraySum = accumulate(nums.begin(), nums.end(), 0);
        int arraySum = 0;
        for (int i = 0; i < nums.size(); i++) {
            arraySum += nums[i];
        }
        return totalSum - arraySum;
    }
};

參考：
#268. Missing Number