2025. 分割數組的最多方案數

給你一個下標從 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?使得上述兩個條件都滿足。

示例 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] 。
有四種方法分割數組。

提示：

• n == nums.length
• 2 <= n <= $10^5$
• $?10^5$ <= k, nums[i] <= $10^5$

解題思路

對于 nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]

我們把nums[0] + nums[1] + ... + nums[pivot - 1] 稱為front，后半部分nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]稱為back，整個數組的總和為sum。

維護一個數組的前綴和pre

1. 當不改變數組的時候，只有滿足sum[i]*2=sum的前綴和，才能成為一種分隔方法
2. 當改變數組的一個元素的時候，我們遍歷所有的元素，嘗試將其改變，維護兩個map，分別代表當前元素前面出現過的前綴和以及后面的前綴和。可以發現當我們嘗試改變元素時，是不會影響前面的前綴和，而是會導致后面的前綴和產生變化d(d為目標元素k與原來元素的差值)。因此對于前邊滿足條件的前綴和，我們的計算公式為sum[i]=sum+d-sum[i]，而對于后面的前綴和計算公式為 sum[i]+d=sum+d-(sum[i]+d)

代碼

class Solution {
public:int waysToPartition(vector<int> nums, int k) {int res(0), n(nums.size());vector<long long> pre(n + 1);map<long long, int> ml;map<long long,int> mr;for (int i = 0; i < n; ++i) {pre[i + 1] = pre[i] + nums[i];if(i+1<n)mr[pre[i+1]]++;}long long sum = pre[n];if (sum%2==0)res=mr[sum/2];for (int i = 1; i <= n; ++i) {long long d=k-nums[i-1],new_sum=sum+d;if (new_sum%2==0){res=max(res,ml[new_sum/2]+mr[new_sum/2-d]);}ml[pre[i]]++;mr[pre[i]]--;}return res;}
};