# 2025. 分割数组的最多方案数

### 题目地址(2025. 分割数组的最多方案数)

<https://leetcode-cn.com/problems/maximum-number-of-ways-to-partition-an-array/>

### 题目描述

```
给你一个下标从 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 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/no2re9.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/2025.maximum-number-of-ways-to-partition-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.