題目：

官網題目連結

根據題目敘述，會給一個由 N 個不同整數組成的陣列 A。該陣列包含 [1~(N+1)] 範圍內的整數，這表示正好缺少一個 [1~(N+1)] 的元素，你必須找出他。
例如輸入 A=[2, 3, 1, 5] ，答案應為 4。

  • N 是範圍 [1~100000] 的整數。
  • 陣列 A 裡的元素都是不重複的。
  • 陣列 A 裡的元素都是範圍 [1~(N+1)] 的整數

解法：

也許你一開始會想到排序後遍歷，但排序需要 O(Nlog N)，所以顯然應該有更好的解法。

再來也許會想到定義一個鍵為 1~(N+1) 的結果陣列，只要遍歷到就從結果陣列中刪除，那麼最後剩下的那個就是答案，這樣的時間複雜度似乎已達標，但是空間是否能用得更少呢?

觀察題目可以發現 1~(N+1) 其實就是等差為 1 的等差數列，那麼我們其實一開始就可以預期他們的總和是多少了，只要用預期總和去減 A 的所有元素就能求解。
這邊需要注意的是公式不要套錯，因為題目其實有少給你 1 個元素，所以正確的長度和高度應是 A 的元素數量再 +1。

像這樣用公式解就能降低空間複雜度到 O(1)。
雖然題目主旨是時間複雜度

  • 時間複雜度 O(N)
  • 空間複雜度 O(1)

PHP 程式碼：