主題
題目連結：
題目意譯：
你被給定一陣列 nums 其由 n 個正整數所組成。你計算出陣列中所有非空的連續子陣列各自的總和，並將這些總和按照非遞減順序排序，創造出一個擁有 n × (n + 1) / 2 個數字的新陣列。
回傳新陣列中索引值 left（含）到索引值 right（含）之總和，其中索引值從 1 開始數。由於答案可能是一個很大的數字，將其模 10 ^ 9 + 7 後再回傳。
限制：
n == nums.length
1 ≦ nums.length ≦ 1000
1 ≦ nums[i] ≦ 100
1 ≦ left ≦ right ≦ n × (n + 1) / 2
範例測資：
範例 1：
輸入： nums = [1,2,3,4], n = 4, left = 1, right = 5
輸出： 13
解釋： 所有子陣列各自的總和為 1 、 3 、 6 、 10 、 2 、 5 、 9 、 3 、 7 、 4。將它們按照非遞減順序排序後，我們得到新陣列 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]。從索引值 le = 1 到 ri = 5 的數字總和為 1 + 2 + 3 + 3 + 4 = 13。
範例 2：
輸入： nums = [1,2,3,4], n = 4, left = 3, right = 4
輸出： 6
解釋： 給定的陣列與範例 1 相同。我們得到新陣列 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]。從索引值 le = 3 到 ri = 4 的數字總和為 3 + 3 = 6。
範例 3：
輸入： nums = [1,2,3,4], n = 4, left = 1, right = 10
輸出： 50
解題思維：
雖然窮舉所有子陣列求各自總和後排序再求解是可行的，不過時間複雜度無論如何都是 O(n ^ 2 × log(n))。而我們實際上可以做得更好一點。
將 nums = [1, 2, 3, 4] 中的子陣列分類為如下：
以 nums[0] = 1 開頭：[1] 、 [1, 2] 、 [1, 2, 3] 、 [1, 2, 3, 4]；
以 nums[1] = 2 開頭：[2] 、 [2, 3] 、 [2, 3, 4]；
以 nums[2] = 3 開頭：[3] 、 [3, 4]；
以 nums[3] = 4 開頭：[4]。
而各自的總和為：
以 nums[0] = 1 開頭：1 、 3 、 6 、 10；
以 nums[1] = 2 開頭：2 、 5 、 9；
以 nums[2] = 3 開頭：3 、 7；
以 nums[3] = 4 開頭：4。
可以看到每一種開頭形成的子陣列集合之總和是一個由小排到大的數列。
這時照著這題使用優先佇列（Priority Queue）來將所有數列合併在一起就變成了與一開始的 O(n ^ 2 × log(n)) 相同之結果（時間也一樣）。
不過此時我們可以看到我們每次合併的時候是拿所有數列中當前最小值，因此第 right + 1 個之後（含）的全部都是不必要的，所以不用合併這之後的數字。因此時間複雜度變成了與 right 相關，即 O(right × log(n))。
但是我們可以做得更好：
假設我們知道 left 固定是 1 且 right 為 r（稱此為 Sr，r 為任意值）的解法，則所求為 Sright - Sleft-1（將 S0 視為 0）。
那要怎麼算出 Sr 呢？首先我們把 nums 的前綴和（Prefix Sums）求出來存在於一陣列 P 中，其中 P[0] = 0 、 P[i] = nums[0] + …… nums[i - 1]（i > 0）；並求出前綴和的前綴和並存於另一陣列 P'，其中 P'[0] = 0 、 P'[i] = P[0] + …… + P[i - 1] （i > 0）。
然後再求出我們知道所有子陣列各自的總和第 r 個的數值為 X。參見這題，而我們這題因為任何子陣列 nums[x] ～ nums[y] 之總和可以轉換成前綴和陣列中的兩數之差 P[y] - P[x - 1]，因此可以對前綴和執行該題的作法而得到第 r 大的子陣列總和。
而該題求出第 r 大的子陣列總和涉及到了雙指標（Two Pointers）的作法（即該題中的 i 和 j 兩個指標），其求出了所有總和 ≦ M 的子陣列數量。
接著我們可以利用基本上一樣的精神來求出所求總和 ≦ M 的子陣列的總和——也就是對每個 j 值（0 ≦ j < n），求出最小的 i（0 ≦ i ≦ j + 1）值滿足 P[j + 1] - P[i] ≦ X。因此對於該 j 值我們可以知道以 nums[j] 結尾的子陣列且總和 ≦ X 的那些子陣列之總和，即
P[j + 1] * (j - i + 1) - (P'[j + 1] - P'[i])
（後面的部分是要去掉以 nums[j - 1] 、 nums[j - 2] 、 ……開頭的子陣列）
上述 i 、 j 雙指標的過程結束後（假設該值為 S），此時 S 並不等於 Sr，因為我們把子陣列總和 = X 的「所有」子陣列都算進來了。
因此我們需要把多餘的減掉，也就是用上面求總和 ≦ M 的子陣列數量的相同方式求出總和 ≦ X 的子陣列，將該值減去 r 個便可以得到我們多算的數量。再將其乘以 X 後，就得到了多算的子陣列之總和。將其從 S 中減去便可以得到 Sr。
因此我們的所求為 Sright - Sleft-1。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
