LeetCode 题解工作台
分割数组的方案数
给你一个下标从 0 开始长度为 n 的整数数组 nums 。 如果以下描述为真，那么 nums 在下标 i 处有一个 合法的分割 ： 前 i + 1 个元素的和 大于等于 剩下的 n - i - 1 个元素的和。 下标 i 的右边 至少有一个 元素，也就是说下标 i 满足 0 。 请你返回 nums…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 前缀和
答案摘要
我们首先计算数组 的总和 ，然后遍历数组 的前 个元素，用变量 记录前缀和，如果 $t \geq s - t$，则将答案加一。 遍历结束后，返回答案即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 前缀和 题型思路
题目描述
给你一个下标从 0 开始长度为 n 的整数数组 nums 。
如果以下描述为真，那么 nums 在下标 i 处有一个 合法的分割 ：
- 前
i + 1个元素的和 大于等于 剩下的n - i - 1个元素的和。 - 下标
i的右边 至少有一个 元素，也就是说下标i满足0 <= i < n - 1。
请你返回 nums 中的 合法分割 方案数。
示例 1：
输入：nums = [10,4,-8,7] 输出：2 解释： 总共有 3 种不同的方案可以将 nums 分割成两个非空的部分： - 在下标 0 处分割 nums 。那么第一部分为 [10] ，和为 10 。第二部分为 [4,-8,7] ，和为 3 。因为 10 >= 3 ，所以 i = 0 是一个合法的分割。 - 在下标 1 处分割 nums 。那么第一部分为 [10,4] ，和为 14 。第二部分为 [-8,7] ，和为 -1 。因为 14 >= -1 ，所以 i = 1 是一个合法的分割。 - 在下标 2 处分割 nums 。那么第一部分为 [10,4,-8] ，和为 6 。第二部分为 [7] ，和为 7 。因为 6 < 7 ，所以 i = 2 不是一个合法的分割。 所以 nums 中总共合法分割方案受为 2 。
示例 2：
输入：nums = [2,3,1,0] 输出：2 解释： 总共有 2 种 nums 的合法分割： - 在下标 1 处分割 nums 。那么第一部分为 [2,3] ，和为 5 。第二部分为 [1,0] ，和为 1 。因为 5 >= 1 ，所以 i = 1 是一个合法的分割。 - 在下标 2 处分割 nums 。那么第一部分为 [2,3,1] ，和为 6 。第二部分为 [0] ，和为 0 。因为 6 >= 0 ，所以 i = 2 是一个合法的分割。
提示：
2 <= nums.length <= 105-105 <= nums[i] <= 105
解题思路
方法一：前缀和
我们首先计算数组 的总和 ，然后遍历数组 的前 个元素，用变量 记录前缀和，如果 ，则将答案加一。
遍历结束后，返回答案即可。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def waysToSplitArray(self, nums: List[int]) -> int:
s = sum(nums)
ans = t = 0
for x in nums[:-1]:
t += x
ans += t >= s - t
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each element is processed once for prefix sums and comparisons. Space complexity is O(1) if using a running sum variable instead of a full prefix sum array. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Focus on array plus prefix sum pattern rather than naive double loops.
- question_mark
Check that both left and right partitions are non-empty when identifying valid splits.
- question_mark
Optimize for linear time; repeated summation signals inefficiency.
常见陷阱
外企场景- error
Forgetting to exclude the last index since the right partition must be non-empty.
- error
Recomputing sums for every split instead of using a prefix sum approach.
- error
Using extra space unnecessarily by storing all prefix sums instead of running totals.
进阶变体
外企场景- arrow_right_alt
Count splits where left sum must strictly exceed right sum instead of >=.
- arrow_right_alt
Allow multiple splits per index if the array has repeated values affecting sums.
- arrow_right_alt
Compute the maximum number of splits achievable in any continuous subarray.