Example 1
Input: [3,0,1]Output: 2
Example 2
Input: [9,6,4,2,3,5,7,0,1]Output: 8
題目理解（必須讀三次 徹底理解含義 條件是什麼，問題是什麼）
第一次理解：
給你一個數組 大小是n，然後尋找缺失一個數，這不是有題目有問題嗎一個都不缺？
第二次理解：
條件：
給你一個數組，含有n個元素，每個元素都不重複，對每元素o到順編號 大小必然是n+1個 現在大小是n個說明少了一個元素。
第三次理解：
給你 編號0到n的n+1個數，然後刪除一個 組成n個數據 尋找缺失這一個元素
分類：
鴿巢原理：
10只鴿子放進9個鴿籠，那麼一定有一個鴿籠放進了至少兩隻鴿子
鴿巢原理
如果不允許重複 必須丟失其中一個有編號的鴿子
分析1
首先想到是：
如果是有序連續數據，（[0,1,3] n=3,缺少 2）
遍歷當有元素是x,下個元素是y，兩者相差必然是1 如果不是，x+1就是缺失元素
如果到了最後一個元素缺失就是元素n （例如【0，1，2，3 】 n=4 缺少 4 ）
步驟
現在是無序的，數值大小n確定了
通過數據公式計算 miss=(1+n)*n/2-sum
public int missingNumber(int[] nums)
{
int n = nums.length;
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += nums[i];
}
return (1 + n) * n / 2 - sum;
}
空間複雜度0 (1）
時間複雜度:0(n)
優化：
1 每個元素+1 變成下一個元素，通過異或消除重複數據也可以 時間複雜度沒變。
2 題目變形：--折半查找
1 Find the missing number in a sorted array of limited range
https://www.geeksforgeeks.org/find-missing-number-sorted-array-limited-range/
2 find-lost-element-from-a-duplicated-array
https://www.geeksforgeeks.org/find-lost-element-from-a-duplicated-array/
尋找缺失2個元素 Find Two Missing Numbers
Given an array of n unique integers where each element in the array is in range [1, n].
The array has all distinct elements and size of array is (n-2).
Hence Two numbers from the range are missing from this array.
Find the two missing numbers.
Examples:
Input : arr[] = {1, 3, 5, 6}, n = 6
Output : 2 4
Input : arr[] = {1, 2, 4}, n = 5
Output : 3 5
Input : arr[] = {1, 2}, n = 4
Output : 3 4
題目：
連續的數字 從1到n ，缺失了2個數 從n變成 n-2 尋找缺失的2個數
知道：已經數組大小n和本來大小n+2，求缺少2個
分析：
假設缺失數值 x，和y
用上面題目的思路 方法不能直接定位缺失那2個元素 n(n+1)/2-sum =x+y
Input : 1 3 5 6, n = 6
Sum of missing integers = n*(n+1)/2 - (1+3+5+6) = 6.
（舍）
首先想到是
構建一個1到n+2數組 S，遍歷該數值S 如果在原來數值A不存在 那就是結果
空間複雜度0 (N）
時間複雜度:0(N*n)
（舍）
因為無順 也不能 強行用折半查找
沒思路了進入衚衕
重新看你思路
網上給出答案是數據公式計算 https://www.geeksforgeeks.org/find-two-missing-numbers-set-1-an-interesting-linear-time-solution/ 這個沒太看懂 是規律
XOR
https://www.geeksforgeeks.org/find-two-missing-numbers-set-2-xor-based-solution/
好吧沒看明白
類似題尋找重複題目
閱讀更多 JiaGouS 的文章
