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 nnums[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]改成kpres就发生了变化。具体来说pres[i], pres[i1], ...全部都会变且变化的增幅一致都是k - nums[i]同理total也变了。total变化倒是容易求新的 total 旧的 total k - nums[i]其中nums[i]为变化前的值。但是pres里一系列值都变了怎么搞关键在于按pivot与被修改位置i的左右关系分类讨论因为前缀和的变化是以修改点为分界的分段行为情形 Apivot 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的项。情形 Bpivot 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。因此一开始left为空right装入全部pres[:n-1]对应pivot 0所有合法 pivot 都在 right 侧且i 0时pivot 0不存在left为空是正确的每次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从而自动排除了总和为奇数、无法均分的非法情形无需显式判奇偶。代码语言支持Python3class 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 # 情形 Apivot i左半不含修改元素查 left # 情形 Bpivot 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
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 nnums[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]改成kpres就发生了变化。具体来说pres[i], pres[i1], ...全部都会变且变化的增幅一致都是k - nums[i]同理total也变了。total变化倒是容易求新的 total 旧的 total k - nums[i]其中nums[i]为变化前的值。但是pres里一系列值都变了怎么搞关键在于按pivot与被修改位置i的左右关系分类讨论因为前缀和的变化是以修改点为分界的分段行为情形 Apivot 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的项。情形 Bpivot 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。因此一开始left为空right装入全部pres[:n-1]对应pivot 0所有合法 pivot 都在 right 侧且i 0时pivot 0不存在left为空是正确的每次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从而自动排除了总和为奇数、无法均分的非法情形无需显式判奇偶。代码语言支持Python3class 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 # 情形 Apivot i左半不含修改元素查 left # 情形 Bpivot 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
