題目：

官網題目連結

根據題目敘述，會給一個由 N 個不同整數組成的非空陣列 A。遍歷到 A 的任一非 0 索引 P 時，會將陣列分成 A[1], A[2],…, A[P−1] 以及 A[P]、A[P+1],…, A[N−1] 兩個部分，其差異指的就是這兩部分各自加總後相減的絕對值。

例如輸入 A=[3, 1, 2, 4, 3] 時，可能的 P 值就會是 1~4，且他們的差異會是:

  1. P = 1，差異 = |3 − 10| = 7 (3 vs 1+2+4+3)
  2. P = 2，差異 = |4 − 9| = 5 (3+1 vs 2+4+3)
  3. P = 3，差異 = |6 − 7| = 1
  4. P = 4，差異 = |10 − 3| = 7

你的方法必須能吃這個陣列，並返回其中最小的差異，以上述例子來看就是 1

  • N 是範圍 [2~100000] 的整數。
  • 陣列 A 裡的元素都是範圍 [-1000~1000] 的整數

解法：

這題敘述挺長的，有可能會一時不知道怎麼下手，但其實原則很簡單，就是一樣想辦法遍歷一次就做完。
我們會發現從 P 到 P+1 時，相當於右邊減去 A[P]，而左邊加上 A[P]，所以你能遍歷一次就找出所有差異值，
那麼只需要多一個變數來存最小差異值就好。

陷阱在於 [1000, -1000]，你如果沒處理好的話就會算出 0，但其實答案應該是 2000。

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

PHP 程式碼：