題目：

官網題目連結

根據題目敘述，會給一個包含 N 個元素的非空陣列 A。你必須檢查 A 中是否包含所有 1~N 的整數值且不重複(其實這有點廢話，因為當滿足包含所有 1~N 的整數時本來就不可能有重複)

例如輸入 A=[4, 1, 3, 2]，滿足所有 1~4 且不重複，所以回傳 1。
而如果輸入 A=[4, 1, 3]，不滿足所有 1~3 且不重複，所以回傳 0。

  • N 是範圍 [1~100000] 的整數。
  • 陣列 A 裡的所有元素都是範圍 [1~1000000000] 的整數

解法：

這邊容易疏忽的點應該是並不保證餵進來的陣列其值都不重複，所以你不能用等差數列來解，依然需要紀錄走了哪些合法值，所以空間複雜度只能 O(N)。

再來由於一樣要追求遍歷一次就做完，所以我們需要找到規律，能先檢查的就是當發生重複(也就是當前遍歷值是已記錄過得合法值)時可以直接回傳 0，也就表示如果成功遍歷完一次 A ，就能確保 A 是元素不重複的陣列，也就能確保當我們紀錄的不重複合法值陣列總數等同於其內部的最大元素值時，就代表符合需求。

因為有點饒舌所以用範例說明，當輸入 A=[4, 1, 3, 2] 時，我們遍歷一遍確保都不重複，並且會得到另一個不重複合法值陣列 B=[4, 1, 3, 2]，然後當 B 的元素總數 4 剛好等於他最大的元素 B[0]=4 時，就代表是正確的。

由於你邊遍歷就可以邊收集最大元素值了，所以總共只要遍歷一次就好。

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

PHP 程式碼：