主題
題目連結(jié)：
題目意譯：
一個整數(shù)陣列的分切是「好的」，代表：
陣列被分切成三個非空的連續(xù)子陣列——從左至右依序稱為 left 、 mid 和 right。
left 的元素總和小於等於 mid 的元素總和，而 mid 的元素總和小於等於 right 的元素總和。
給定 nums，其為一非負(fù)整數(shù)陣列，回傳分切 nums 的好方式之?dāng)?shù)量。由於答案可能會太大，因此先將其模 10 ^ 9 + 7 後再回傳。
限制：
3 ≦ nums.length ≦ 10 ^ 5
0 ≦ nums[i] ≦ 10 ^ 4
範(fàn)例測資：
範(fàn)例 1：
輸入： nums = [1,1,1]
輸出： 1
解釋： 唯一一個好的 nums 分切方式為 [1] [1] [1]。
範(fàn)例 2：
輸入： nums = [1,2,2,2,5,0]
輸出： 3
解釋： 有三個好的 nums 分切方式：
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]
範(fàn)例 3：
輸入： nums = [3,2,1]
輸出： 0
解釋： 沒有好的 nums 分切方式存在。
解題思維：
（令 n = nums.length）
首先，窮舉第一個部分的結(jié)尾到哪個元素。即窮舉 nums[i]，使得 nums[0] ～ nums[i] 為 left 這個部分。
對於每個 nums[i]，先求出第二部分的結(jié)尾最靠近 nums[i] 的地方，也就是求得 nums[j] 使得 nums[i + 1] ～ nums[j] 為 mid 之部分、mid 之總和 ≧ left 之總和（這部分可以利用前綴和（Prefix Sums）求得，如這題）且 j 盡可能小。如果沒有這樣的 j 值，將 j 設(shè)為 n（跟下面的計算有關(guān)）。
最後再對 nums[j] 求出 nums[k] 使得 nums[k + 1] ～ nums[n - 1] 為 right 之部分、right 之總和 ≧ mid 之總和且 k 盡可能地大。如果沒有這樣的 k 值，將 k 設(shè)為 j（跟下面的計算有關(guān)）。
而我們便可以看到 k - j 即是對於 nums[i] 來說，好的分切方式之?dāng)?shù)量。而如果過程中找不到 nums[j] 或是 nums[k]，可以看到此時的 k - j 會是 0（根據(jù)上面的例外處理）。
當(dāng)然，如果每次都真的這麼求的話，時間會是 O(n ^ 3)。
但是我們可以觀察到，由於 nums 中的數(shù)字都是非負(fù)的，因此 nums[i + 1] 的 j 和 k 之值必定不會小於 nums[i] 的 j 和 k（因?yàn)?left 的總和不會變?。Ｒ虼宋覀冊诟F舉 nums[i]，從 nums[i] 到 nums[i + 1] 時，我們可以繼承前次的 j 和 k 值繼續(xù)往右（即讓 j 和 k 繼續(xù)變大）。
這樣一來，i 、 j 、 k 都是遞增的，一路遞增到 n 為止，再加上每一次求出每個部分總和只需要 O(1)（因?yàn)槭褂昧饲熬Y和的技巧）。因此時間降為 O(n)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
