LeetCode 题解工作台
分割数组的最多方案数
给你一个下标从 0 开始且长度为 n 的整数数组 nums 。 分割 数组 nums 的方案数定义为符合以下两个条件的 pivot 数目： 1 nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + .…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们可以先预处理得到数组 对应的前缀和数组 ，其中 表示数组 的和。那么数组所有元素之和为 $s[n - 1]$。 如果不修改数组 ，那么两个子数组的和相等的条件是 $s[n - 1]$ 必须为偶数，如果 $s[n - 1]$ 为偶数，那么我们求出 $ans = \frac{right[s[n - 1] / 2]}{2}$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 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.length2 <= n <= 105-105 <= k, nums[i] <= 105
解题思路
方法一：前缀和 + 哈希表
我们可以先预处理得到数组 对应的前缀和数组 ，其中 表示数组 的和。那么数组所有元素之和为 。
如果不修改数组 ，那么两个子数组的和相等的条件是 必须为偶数，如果 为偶数，那么我们求出 。
如果修改数组 ，那么我们可以枚举每一个修改的位置 ，将 修改为 ，那么数组总和的变化量 ，此时 左侧部分的和保持不变，那么合法的分割要满足 ，即 ；而右侧部分的每个前缀和都增加了 ，那么合法的分割要满足 ，即 。我们用哈希表 和 分别记录左侧部分和右侧部分每个前缀和出现的次数，那么我们可以求出 。
最后，我们返回 即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def waysToPartition(self, nums: List[int], k: int) -> int:
n = len(nums)
s = [nums[0]] * n
right = defaultdict(int)
for i in range(1, n):
s[i] = s[i - 1] + nums[i]
right[s[i - 1]] += 1
ans = 0
if s[-1] % 2 == 0:
ans = right[s[-1] // 2]
left = defaultdict(int)
for v, x in zip(s, nums):
d = k - x
if (s[-1] + d) % 2 == 0:
t = left[(s[-1] + d) // 2] + right[(s[-1] - d) // 2]
if ans < t:
ans = t
left[v] += 1
right[v] -= 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on a single pass to compute prefix sums plus O(n) operations for scanning and hash map updates, giving roughly O(n) overall. Space complexity is O(n) for prefix sums and hash maps to track counts of sums. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate recognizes the need for prefix sums instead of brute-force pivot checking.
- question_mark
Candidate proposes hash map for counting prefix sums efficiently.
- question_mark
Candidate identifies that changing one element can create additional pivot indices and discusses simulation.
常见陷阱
外企场景- error
Not considering the unchanged array as a candidate for maximum pivots.
- error
Incorrectly updating prefix sums after a simulated change, leading to wrong pivot counts.
- error
Overlooking negative numbers or zeros affecting partition equality checks.
进阶变体
外企场景- arrow_right_alt
Counting pivots without any allowed element change, purely based on original array sums.
- arrow_right_alt
Finding maximum pivots when multiple elements can be changed instead of just one.
- arrow_right_alt
Computing partitions where the left sum minus right sum equals a target difference other than zero.