主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始的長度為 n 之整數陣列 nums。nums 的分割方法數為滿足以下兩個情況的基準點索引值 pivot 之數目：
1 ≦ pivot < n
nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]
你同樣也被給定一整數 k。你可以選擇把 nums 其中一個元素之值變為 k，或是選擇讓陣列保持不變。
回傳在改變最多一個元素的情況下，最大可能的 nums 分割方法數。
限制：
n == nums.length
2 ≦ n ≦ 10 ^ 5
-10 ^ 5 ≦ k, nums[i] ≦ 10 ^ 5
範例測資：
範例 1：
輸入： nums = [2,-1,2], k = 3
輸出： 1
解釋： 其中一個最佳策略是將 nums[0] 變為 k。陣列變為 [3,-1,2]。
有一種可以分割陣列的方式：
- 對於 pivot = 2，我們有分割為 [3,-1 | 2]：3 + -1 == 2.
範例 2：
輸入： nums = [0,0,0], k = 1
輸出： 2
解釋： 最佳策略是使陣列不變。
有兩種可以分割陣列的方式：
- 對於 pivot = 1，我們有分割為 [0 | 0,0]：0 == 0 + 0.
- 對於 pivot = 2，我們有分割為 [0,0 | 0]：0 + 0 == 0.
範例 3：
輸入： nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
輸出： 4
解釋： 其中一個最佳策略是將 nums[2] 變為 k。陣列變為 [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14].
有四種可以分割陣列的方式。
解題思維：
先將陣列 nums 的前綴和（Prefix Sums）計算出來（如這題），並令一陣列 P 滿足 P[0] = 0 且 P[i] = nums[0] + nums[i - 1]（nums 前 i 個數字之和，此即前綴和）。
現在我們可以看到對於某個索引值 i，其左側 nums[0] + …… + nums[i - 1] 之值正好為 P[i]；而右側 nums[i] + …… + nums[n - 1] 之值為 P[n] - P[i]。因此當 P[i] = P[n] - P[i]（也就是 P[n] - 2P[i] = 0）時，索引值 i 即為一個合法的 pivot，即形成了一個分割。
以下我們稱索引值 i 時計算出來的 P[n] - 2P[i] 之值為 Xi。
接著我們先掃過一遍 nums 求出所有在不更動任何元素下有多少分割數（利用上面提及的 Xi 來判斷每個索引值是不是 pivot），我們叫此數為 M。
現在我們觀察當我們改變 nums[x] 之值為 k 時會發生什麼事情：
已知對於想要計算 Xi 的索引值 i，變更前的 Xi 之值為 P[n] - 2P[i]。
如果 i ≦ x，則其 Xi 之值將變為 P[n] - 2P[i] + k - nums[x]；
如果 i > x，則其 Xi 之值將變為 P[n] - 2P[i] + nums[x] - k。
因此改變 nums[x] 為 k 之後，會是 pivot 將變成是原先 Xi 之值為 nums[x] - k（對於 i ≦ x）以及 k - nums[x]（對於 i ＞ x）的那些索引值（因為如此一來，舊的 Xi 之值變化後才會變為 0）。
因此我們可以定義兩個雜湊表（Hash Table）L 以及 R 用來儲存索引值 i 時其左側（0 ～ i）和右側（i + 1 ～ n）各自有哪些種類的 Xi 之值（其中 L[x] 代表有多少個位置其 Xi 之值 = x；R[x] 同理）。在最一開始先算 nums 未變化前的分割數 M 時可以順便求得最後一個位置 n - 1 的 L 、 R（此時 L 包含所有 Xi 之值且 R 為空）。
接著從最後一個位置 n - 1 往回掃到索引值 0（這邊記得包括索引值 0，因為我們也可以使 nums[0] 變為 k，儘管 pivot 根據題目定義不可能是 0）。過程中對於每個索引值 i 做以下事情：
根據上面對於把 nums[i] 變為 k 的觀察，得到將位置 i 變化後可得的分割數 Mi，即 L[nums[i] - k] + R[k - nums[i]]；
接著因為我們要進行到下一個索引值 i - 1，我們需要它的 L 、 R 之內容。而這可以從索引值 i 的 L 、 R 推得，因為兩個位置只差 Xi 而已。因此將 L[Xi] 減 1 、R[Xi] 加 1 即可得到。
最後我們比較 M 、 Mn-1 、 Mn-2 、 …… 、 M0 等等誰大即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
