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 <= 105
• -105 <= k, nums[i] <= 105

计算出 nums 的前缀和 sum，记所有元素的和为 tot。

对于不修改的情况，合法分割相当于要满足 sum}[i] = \textit{tot}-\textit{sum}[i]，即 sum}[i]=\dfrac{\textit{tot} }{2。

对于修改的情况，枚举修改的元素，记变化量 d=k-\textit{nums}[i]，这一修改操作对于 i 左侧的前缀和是没有影响的，因此合法分割相当于要满足 sum}[i] = \textit{tot}+d-\textit{sum}[i]，即 sum}[i]=\dfrac{\textit{tot}+d}{2；而对于 i 右侧的前缀和，每个前缀和都增加了 d，因此合法分割相当于要满足 sum}[i]+d = \textit{tot}+d-(\textit{sum}[i]+d)，即 sum}[i]=\dfrac{\textit{tot}-d}{2。

我们可以在枚举 nums}[i] 的同时，用两个哈希表动态维护 i 左右前缀和的个数，从而做到对每个 nums}[i] 在 O(1) 的时间计算出合法分割数，因此总的时间复杂度为 O(n)。

func waysToPartition(nums []int, k int) (ans int) {
	n := len(nums)
	sum := make([]int, n)
	sum[0] = nums[0]
	cntR := map[int]int{}
	for i := 1; i < n; i++ {
		sum[i] = sum[i-1] + nums[i]
		cntR[sum[i-1]]++
	}
	tot := sum[n-1]
	if tot%2 == 0 {
		ans = cntR[tot/2] // 不修改
	}
	cntL := map[int]int{}
	for i, s := range sum {
		if d := k - nums[i]; (tot+d)%2 == 0 {
			ans = max(ans, cntL[(tot+d)/2]+cntR[(tot-d)/2]) // 修改 nums[i]
		}
		cntL[s]++
		cntR[s]--
	}
	return
}

func max(a, b int) int { if b > a { return b }; return a }