# 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)$

- 程式碼

    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)$

- 程式碼

    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;
        }
    };