---
# System prepended metadata

title: LeetCode 268. Missing Number

---

# LeetCode 268. Missing Number
[LeetCode 268. Missing Number](https://leetcode.com/problems/missing-number) (難度 通過率)
<!-- 
(<font color=#00AF9B>Easy</font> 53.8%) 
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
 -->
    
- 限制 :
    
    <ul>
    <li><code>n == nums.length</code></li>
    <li><code>1 <= n <= 10^4</code></li>
    <li><code>0 <= nums[i] <= n</code></li>
    <li><code>All the numbers of nums are unique.</code></li>
    </ul>

- Solution 1 
    這題要找的是數列當中哪一個數字不在。
    解法有很多，第一個是去匹配哪一個數字與陣列index 不符即為答案。
    - 時間複雜度: $O(nlogn)$
    - 空間複雜度: $O(1)$

- 程式碼
    ```c++=
    class Solution {
    public:
        int missingNumber(vector<int>& nums) {

            sort(nums.begin(),nums.end());
            for(int i=0;i<nums.size();i++)
            {
                if(i!=nums[i]) return i;
            }
            return nums.size();
        }
    };
    ```

- Solution 2
    第二種解法是先直接把最大值成起來，之後再扣掉，最後留下來的就是那個不存在的數字
    - 時間複雜度: $O(n)$
    - 空間複雜度: $O(1)$
    
- 程式碼
    ```cpp=
    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
          long size = nums.size();
          long result = (size+1)*size/2;

          for(auto& i:nums)
          {
            result -= i;
          }
          return result;
        }
    };
    ```
