主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始的 n 個整數之陣列 differences，其代表著在一個隱藏的長度 (n + 1) 之數列中每對連續整數之差值。更正式地說，稱該隱藏數列為 hidden，則我們將會有 differences[i] = hidden[i + 1] - hidden[i]。
你再被給定兩整數 lower 和 upper，其代表著該隱藏數列裡的數值為於一個範圍 [lower, upper]（含端點）之中。
例如，給定 differences = [1, -3, 4] 、 lower = 1 、 upper = 6，代表隱藏數列為長度 4 的數列且其元素值位於 1（含）到 6（含）之間。
[3, 4, 1, 5] 和 [4, 5, 2, 6] 為可能的隱藏數列。
[5, 6, 3, 7] 不可能，因為其包含著大於 6 的元素。
[1, 2, 3, 4] 不可能，因為其差值不符合給定之值。
回傳可能的隱藏數列之總數。如果沒有任何可能的數列，則回傳 0。
限制：
n == differences.length
1 ≦ n ≦ 10 ^ 5
-10 ^ 5 ≦ differences[i] ≦ 10 ^ 5
-10 ^ 5 ≦ lower ≦ upper ≦ 10 ^ 5
範例測資：
範例 1：
輸入： differences = [1,-3,4], lower = 1, upper = 6
輸出： 2
解釋： 可能的隱藏數列為以下：
- [3, 4, 1, 5]
- [4, 5, 2, 6]
因此，我們回傳 2。
範例 2：
輸入： differences = [3,-4,5,1,-2], lower = -4, upper = 5
輸出： 4
解釋： 可能的隱藏數列為以下：
- [-3, 0, -4, 1, 2, 0]
- [-2, 1, -3, 2, 3, 1]
- [-1, 2, -2, 3, 4, 2]
- [0, 3, -1, 4, 5, 3]
因此，我們回傳 4。
範例 3：
輸入： differences = [4,-7,2], lower = 3, upper = 6
輸出： 0
解釋： 沒有可能的隱藏數列存在。因此，我們回傳 0。
解題思維：
首先第一個觀察：
可以看到當我們設定好隱藏數列的「第零項」（即 hidden[0]）時，接下來每一項便可以由 differences 推出來。例如 differences = [1,-3,4]，而我們假設第零項的數值是 3，則：
第一項為 3 + 1 = 4、
第二項為 4 - 3 = 1、
第三項為 1 + 4 = 5。
第二個觀察：
當我們把第零項 + 1，每一項也會跟著 + 1。
根據以上兩個觀察加上數列中所有的數值都要位於 [lower, upper] 這個範圍中的定義，我們可以推論出：
令整數數列最小值為 m、最大值為 M，因此可能的隱藏數列之個數即為
(upper - lower) - (M - m) + 1
其意義就是——存在一個數列第零項為 x，使得數列最小值恰好為 lower（即 m = lower 的情況）；且也存在一數列第零項為 y，使得數列最大值恰好為 upper（即 M = upper 的情況）。而根據觀察二，可能的數列就只會有 y - x + 1 個。
而想當然爾，當 (upper - lower) < (M - m) 時，代表著不論如何都無法讓數字範圍都落在 [lower, upper] 中。因此此時應回傳 0。
可是問題是 M 、 m 是未知數，怎麼辦？此時我們可以回到第二個觀察，便可以推論得到：第零項 = 0 時的最大值與最小值之差，會與第零項 = 1 時的最大值與最小值之差、第零項 = 2 時的最大值與最小值之差……皆相同。也就是說實際上不管第零項是多少，我們都可以藉由其最大值減去最小值之值來算出 (M - m) 之值。因此便可以根據上面的推論得到所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
