# 2025. 分割数组的最多方案数
### 题目地址(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
```
### 前置知识
* 枚举
* 前缀和
* 哈希表
### 公司
* 暂无
### 思路
题目让我们求经过一顿操作后最多满足左右和相等的索引 pivot 有多少个。
于是我们可以枚举所有的索引 i ，如果我将 i 的值改为 k 那么有多少 pivot。对于每一个 i，我们如何计算有多少 pivot 呢?
显然 pivot 是大于 0 的。
那么如何判断索引 1 是否是一个 pivot 呢？我们只需判断 pres\[i-1] 是否等于 total / 2 即可。其中 pres 是 nums 的前缀和， total 是 nums 总和，也就是 sum(nums)。
那么如何判断索引 2 是否是一个 pivot 呢？还是类似的，判断 pres\[i-1]是否等于 total / 2 即可。
可问题是 pres 发生了变化，具体来说 pres\[2], pres\[3] ... 都变了，变化的增幅也是一致的，同理 total 也是变化了。 total 变化倒容易求，新的 total = 旧的 total + k - nums\[i] 其中 nums\[i]为变化前的值。但是 pres 里一系列的值都变了，怎么搞？
其实我们可以这么做。以题目的 \[2,-1,2] 为例：
* 定义两个哈希表 left 和 right，分别表示当前遍历到的元素的左右侧的前缀和的映射，key 是前缀和的值， value 是出现次数。
* left 初始化为空，right 初始化为 { 2: 1, 1: 1, 3: 1 }，表示前缀和 2，1，3 分别出现了一次。
* 根据 left，right 和 total 我们就能求出将当前索引值改为 k 的 pivot 总数了。left\[total/2] + right\[total/2]。 这是本题的第一个难点。
* 接下来枚举所有的索引，枚举到下一项的是否如何更新 left, right 和 total 呢?这是本题的第二个难点。
1. left\[pres\[i-1]] += 1 right\[pres\[i-1]] -= 1。前提是 i>0。
2. 如果上一次结果是 left\[total/2] + right\[total/2]，那么下一次是多少呢？答案是 left\[(total - nums\[i] + k) / 2] + right\[total - (total - nums\[i] + k) / 2])
其中 **total - nums\[i] + k 是左半部分新的 total，右半部分是 total - 左半部分新的 total。**
### 关键点
* 滚动思想
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def waysToPartition(self, nums: List[int], k: int) -> int:
n, pres = len(nums), list(accumulate(nums))
left, right = defaultdict(int), Counter(pres[:n - 1])
total = pres[-1]
ans = right[total / 2]
for i in range(n):
if i > 0: left[pres[i - 1]] += 1
if i > 0: right[pres[i - 1]] -= 1
ans = max(ans, left[(total - nums[i] + k) / 2] + right[total - (total - nums[i] + k) / 2])
return ans
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：left 和 right 都不会超过 n 项，因此空间复杂度为 $O(n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~s
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
