企业官网建设流程全解析

LeetCode 2025 分割数组的最多方案数：前缀和 + 双哈希表滚动枚举题解

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇以 leetcode 仓库中的 2025.maximum-number-of-ways-to-partition-an-array.md 为骨架，完整讲解力扣第 2025 题《分割数组的最多方案数》的O(n) 双哈希表滚动枚举解法。本题将"前缀和判等"与"至多修改一个元素"两类问题合二为一，是检验你对前缀和、哈希表与增量维护理解深度的优质困难题。读完本文，你将掌握：如何用前缀和判断一个 pivot 是否合法、修改单个元素后前缀和与总和如何系统性变化，以及如何用 left / right 两张哈希表在遍历过程中以 O(1) 增量代价统计出全部方案数。

题目描述

给你一个下标从 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

前置知识

• 枚举
• 前缀和
• 哈希表

本题是该仓库前缀和专题所强调思想的典型延伸：一旦题目出现"连续""分割""子数组和"等关键字，前缀和就应当被列为第一梯队候选技巧。

思路推演：从判定 pivot 到枚举修改位置

第一步：前缀和判定一个 pivot 是否合法

题目让我们求经过一顿操作后，最多满足左右和相等的索引pivot有多少个。于是我们可以枚举所有的索引i：如果我把i的值改为k，那么有多少个pivot是合法的？对于每一个i，我们如何计算有多少个pivot呢？

显然pivot是大于 0 的。设pres为nums的前缀和数组（pres[i] = nums[0] + ... + nums[i]），total = sum(nums)为数组总和。那么：

• 要判断索引 1 是否是一个合法 pivot，只需判断pres[0]是否等于total / 2；
• 要判断索引 2 是否是一个合法 pivot，只需判断pres[1]是否等于total / 2；
• 推广到一般情况：pivot 合法当且仅当pres[pivot - 1] == total / 2。

这是本题的根基：左右和相等，等价于"左边前缀和恰好是总和的一半"。

第二步：修改一个元素后，前缀和发生了什么变化

可问题是，一旦把某个nums[i]改成k，pres就发生了变化。具体来说，pres[i], pres[i+1], ...全部都会变，且变化的增幅一致（都是k - nums[i]）；同理total也变了。total变化倒是容易求：

新的 total = 旧的 total + k - nums[i]

其中nums[i]为变化前的值。但是pres里一系列值都变了，怎么搞？

关键在于按pivot与被修改位置i的左右关系分类讨论，因为前缀和的变化是"以修改点为分界"的分段行为：

情形 A：pivot <= i（左半部分不包含被修改的元素nums[i]）

此时左半部分的和仍是pres[pivot - 1]（未变），右半部分的和变成旧total - pres[pivot - 1] + (k - nums[i])。令左右相等：

pres[pivot - 1] == 旧total - pres[pivot - 1] + k - nums[i] ⇒ pres[pivot - 1] == (旧total + k - nums[i]) / 2

即：在 left 一侧的前缀和中，寻找值等于(旧total + k - nums[i]) / 2的项。

情形 B：pivot > i（左半部分包含被修改的元素nums[i]）

此时左半部分的和变成pres[pivot - 1] + (k - nums[i])，右半部分的和仍为旧total - pres[pivot - 1]。令左右相等：

pres[pivot - 1] + k - nums[i] == 旧total - pres[pivot - 1] ⇒ pres[pivot - 1] == (旧total - k + nums[i]) / 2

即：在 right 一侧的前缀和中，寻找值等于(旧total - k + nums[i]) / 2的项。

两种情形分别对应两种候选 key，这正是"双哈希表"方案的核心来源。

第三步：用 left 和 right 两张哈希表快速计数

有了上面的分类，一个朴素做法是：对每个i，遍历所有pivot计算满足条件的前缀和数量，但这样是 O(n²)，无法通过n <= 10^5的规模。

优化思路是把前缀和的"值 → 出现次数"提前用哈希表存好，查询从 O(n) 降到 O(1)。以题目的[2,-1,2]为例：

• 定义两个哈希表left和right，分别表示"当前遍历到的元素"左右侧的前缀和的映射。key 是前缀和的值，value 是出现次数。
• left初始化为空；right初始化为{2: 1, 1: 1, 3: 1}，表示前缀和2、1、3各出现了一次（即pres[0..1]，对应所有pivot > 0的合法候选位置）。
• 根据left、right和total，我们就能求出将当前索引值改为k的 pivot 总数了：

left[ (total - nums[i] + k) / 2 ] + right[ total - (total - nums[i] + k) / 2 ]

这是本题的第一个难点。其中：

• total - nums[i] + k是修改后新的数组总和；
• left[(total - nums[i] + k) / 2]对应情形 A：左半不含修改元素，左半前缀和必须等于新总和的一半；
• right[total - (total - nums[i] + k) / 2]对应情形 B：左半包含修改元素，此时右半的和是新总和的一半，因此右半在旧前缀和中对应的 key 是旧total - 新total / 2（因为右半和 = 旧total - pres[pivot-1]，令其等于 新total/2，解得pres[pivot-1] = 旧total - 新total/2）。

由于total在代码中始终保存修改前的总和，left与right中存的也都是修改前的原始前缀和，因此两条分支的 key 必须按上述方式分别换算，这正是公式中两个看似不对称的项。

第四步：滚动更新 left、right 与 total

接下来枚举所有索引，枚举到下一项时如何更新left、right和total呢？这是本题的第二个难点。

由于pivot必须满足1 <= pivot < n，合法的分割位置对应前缀和pres[0], pres[1], ..., pres[n-2]（共 n-1 个）。当遍历指针i从 0 逐步走到 n-1 时，前缀和pres[i-1]所属的角色发生变化：当i作为被修改位置时，所有pivot <= i的判定走情形 A（查left），所有pivot > i的判定走情形 B（查right）。因此：

1. 一开始left为空，right装入全部pres[:n-1]，对应pivot > 0（所有合法 pivot 都在 right 侧），且i = 0时pivot <= 0不存在，left为空是正确的；
2. 每次i前进一格，就把pres[i-1]从right中减去一次、加进left中一次（前提是i > 0）。这一增一减正是"滚动"思想的体现——每个前缀和在其生命周期内只被移动一次，全程增量维护，总代价 O(n)。

更新后，对当前的i直接套用第三步的公式计算方案数，与全局答案取 max 即可。

关键点

• 滚动思想：left/right两张哈希表随着枚举位置滚动更新，每个前缀和只被"右减左加"移动一次，从而把枚举修改位置的代价从 O(n²) 降到 O(n)；
• 分类讨论：以pivot与被修改元素i的左右关系划分两种情形，分别得到两个查询 key，缺一不可；
• 浮点 key 的妙用：代码中使用 Python 的/浮点除法，当total + k - nums[i]为奇数时，key 形如x.5，而所有真实前缀和都是整数，哈希查找必然 miss 返回 0，从而自动排除了"总和为奇数、无法均分"的非法情形，无需显式判奇偶。

代码

• 语言支持：Python3

class Solution: def waysToPartition(self, nums: List[int], k: int) -> int: n, pres = len(nums), list(accumulate(nums)) # left: 已枚举过的前缀和（pivot 在左侧的候选） # right: 尚未枚举到的前缀和（pivot 在右侧的候选），初始为全部合法位置 pres[0..n-2] left, right = defaultdict(int), Counter(pres[:n - 1]) total = pres[-1] # 修改前的总和，全程保持不变 # 不改变数组时的方案数：直接统计 pres[pivot-1] == total / 2 的数量 ans = right[total / 2] for i in range(n): # 滚动更新：pres[i-1] 从 right 移入 left if i > 0: left[pres[i - 1]] += 1 right[pres[i - 1]] -= 1 # 新总和的一半 half = (total - nums[i] + k) / 2 # 情形 A（pivot <= i）：左半不含修改元素，查 left # 情形 B（pivot > i）：左半含修改元素，右半和 = 新总和一半，对应旧前缀和 key = total - half，查 right ans = max(ans, left[half] + right[total - half]) return ans

如果你更习惯整数运算，可以显式判断奇偶后使用//整除，语义等价：

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] if total % 2 == 0 else 0 # 不改变数组时，总和为奇则无解 ans //= 2 if total % 2 == 0 else 1 # 注意：这里仅演示思路，统计的是 right[total//2] # 正确写法：ans = right[total // 2] if total % 2 == 0 else 0 ans = right[total // 2] if total % 2 == 0 else 0 for i in range(n): if i > 0: left[pres[i - 1]] += 1 right[pres[i - 1]] -= 1 new_total = total - nums[i] + k if new_total % 2 == 0: half = new_total // 2 ans = max(ans, left[half] + right[total - half]) return ans

代码验证

笔者在本地以 Python3 运行了题解代码，对题目给出的三个示例逐一验证，结果全部通过：

[2, -1, 2] k= 3 => got 1, expect 1 OK [0, 0, 0] k= 1 => got 2, expect 2 OK [22, 4, -25, -20, -15, 15, -16, 7, 19, -10, 0, -13, -14] k= -33 => got 4, expect 4 OK

说明文档中的推导与实现是自洽、可直接运行的。

复杂度分析

令n为数组长度。

• 时间复杂度：O(n)。前缀和计算一次 O(n)；双哈希表的构建与滚动更新全程每个元素只被移动一次，枚举修改位置 O(n)；每次查询均为哈希表 O(1) 查找，故总体 O(n)。
• 空间复杂度：left和right都不会超过 n 项，因此空间复杂度为 O(n)。

总结与延伸

本题是"前缀和判定 + 单点修改 + 滚动哈希表"的组合拳，属于前缀和专题中"利用哈希表存前缀和计数、以 O(1) 代价回答区间/分割类查询"思想的进阶形态。与其配套的基础题型还包括：

• 560. 和为 K 的子数组：用哈希表记录前缀和出现次数，O(n) 统计连续子数组和为 k 的个数，是本题"哈希表 + 前缀和"的直接原型；
• 525. 连续数组：0/1 数组转换为 ±1 前缀和差值问题，体会"前缀和变形"的威力；
• 1371. 每个元音包含偶数次的最长子字符串：前缀和 + 状态压缩的经典组合；
• 1186. 删除一次得到子数组最大和：与本题同属"至多修改/删除一个元素"的变形题家族。

该题在仓库 README.md 与 SUMMARY.md 的题解清单中均有收录，读者可对照仓库中其他题解进一步体会前缀和与哈希表在不同场景下的排列组合。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode