268. Missing Number

---

My Solution

The Key Idea for Solving This Coding Question

輸入陣列 nums 的長度為 n 。且 nums 內的元素為 [0, n] 間的整數。所以有 n+1 個整數要放入 n 個位子中，一定會有一個整數無法放入 nums 中。題目要我們找出 [0, n] 中，沒有被放入 nums 的那個整數。
我們可以先用數學公式

$\frac{(1+n)\cdot n}{2}$ 求得 [0, n] 間所有整數的和 answer。然後，遍歷 nums ，逐一將 nums 中的整數自 answer 中減去。只要我們將 nums 中的所有元素都走過一遍， answer 中最後的值就是沒有被放入 nums 中的整數。

C++ Code

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

        return answer;
    }
};

Time Complexity

$O(n)$

$n$ is the length of nums.

Space Complexity

$O(1)$

Miscellaneous