主題
題目連結：
題目意譯：
一陣列 a 的最小絕對差值定義為 |a[i] - a[j]| 的最小值，其中 0 ≦ i < j < a.length 且 a[i] ≠ a[j]。如果 a 中所有元素相同，則最小絕對差訂為 -1。
例如，陣列 [5,2,3,7,2] 的最小絕對差值為 |2 - 3| = 1。注意其值不是 0 因為 a[i] 與 a[j] 之值必須不同。
你被給定一整數陣列 nums 以及一陣列 queries 其中 queries[i] = [li, ri]。對於詢問 i，計算子陣列 [li……ri] 其包含著 nums 從 0 開始的索引值 li 到 ri 之間的元素（含端點）之最小絕對差值。
回傳一陣列 ans 其中 ans[i] 為第 i 筆詢問之答案。
一子陣列為一個陣列的一個連續元素序列。
|x| 之值定義如下：
x 如果 x ≧ 0。
-x 如果 x < 0。
限制：
2 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 100
1 ≦ queries.length ≦ 2 × 10 ^ 4
0 ≦ li < ri < nums.length
範例測資：
範例 1：
輸入： nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
輸出： [2,1,4,1]
解釋： 詢問之處理為以下：
- queries[0] = [0,1]：子陣列為 [1,3] 且最小絕對差值為 |1 - 3| = 2。
- queries[1] = [1,2]：子陣列為 [3,4] 且最小絕對差值為 |3 - 4| = 1。
- queries[2] = [2,3]：子陣列為 [4,8] 且最小絕對差值為 |4 - 8| = 4。
- queries[3] = [0,3]：子陣列為 [1,3,4,8] 且最小絕對差值為 |3 - 4| = 1。
範例 2：
輸入： nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
輸出： [-1,1,1,3]
解釋： 詢問之處理為以下：
- queries[0] = [2,3]：子陣列為 [2,2] 且最小絕對差值為 -1 因為所有元素相同。
- queries[1] = [0,2]：子陣列為 [4,5,2] 且最小絕對差值為 |4 - 5| = 1。
- queries[2] = [0,5]：子陣列為 [4,5,2,2,7,10] 且最小絕對差值為 |4 - 5| = 1。
- queries[3] = [3,5]：子陣列為 [2,7,10] 且最小絕對差值為 |7 - 10| = 3。
解題思維：
本題可以使用前綴和（Prefix Sums）來做，但是本題的前綴和不是用來「求區間和」（如這題），而是拿來判斷某區間是否存在特定數字。
（以下為了方便，將 nums 的索引值改為從 1 開始）
我們定義 P[i][j] 為 nums[1] ～ nums[i] 中有多少的數字 j，其中 P[0][j] = 0 、 P[i][j] = P[i - 1][j] + (nums[i] 是否為 j) 且 0 ≦ i ≦ nums.length 、 1 ≦ j ≦ 100（即 nums[i] 的數值範圍）。
因此當 P[L][j] ≠ P[R][j]（L ≦ R）時，代表 nums[L + 1] ～ nums[R] 有至少額外出現一次數字 j 。
因此我們掃過每一筆詢問 queries[i] = [li, ri]（注意，這邊的 li 和 ri 索引值仍從 0 開始），然後掃過 1 ～ 100 中所有的數字 j。然後藉由上述的 P[li][j] 與 P[ri + 1][j] 之關係，便可以得到 nums[li + 1] ～ nums[ri + 1] 之間有無數字 j。
將 nums[li + 1] ～ nums[ri + 1] 中有的數字擷取出來（且是按照大小由小到大排序）之後就好辦了，兩兩相鄰數字求差值。而差值中最小的即為此筆詢問之答案。如果擷取出來的數字不到兩個，則此筆詢問最小絕對差值即為 -1。
然後將每筆詢問的答案放入陣列 ans 中即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
