---
tags: leetcode
---

# [268. Missing Number](https://leetcode.com/problems/missing-number/)
---
# My Solution

## The Key Idea for Solving This Coding Question

輸入陣列 `nums` 的長度為 `n` 。且 `nums` 內的元素為 `[0, n]` 間的整數。所以有 `n+1` 個整數要放入 `n` 個位子中，一定會有一個整數無法放入 `nums` 中。題目要我們找出 `[0, n]` 中，沒有被放入 `nums` 的那個整數。
我們可以先用數學公式 ${(1 + n) \cdot n \over 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

<!--
# Test Cases

[3,0,1]

[0,1]

[9,6,4,2,3,5,7,0,1]

[1]

[0]

-->