LeetCode 题解工作台
统计元素和差值为偶数的分区方案
给你一个长度为 n 的整数数组 nums 。 分区 是指将数组按照下标 i （ 0 ）划分成两个 非空 子数组，其中： 左子数组包含区间 [0, i] 内的所有下标。 右子数组包含区间 [i + 1, n - 1] 内的所有下标。 对左子数组和右子数组先求元素 和 再做 差 ，统计并返回差值为 偶数…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·数学
答案摘要
我们用两个变量 和 分别表示左子数组和右子数组的和，初始时 $l = 0$，而 $r = \sum_{i=0}^{n-1} \textit{nums}[i]$。 接下来，我们遍历前 $n - 1$ 个元素，每次将当前元素加到左子数组中，同时从右子数组中减去当前元素，然后判断 $l - r$ 是否为偶数，如果是则答案加一。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个长度为 n 的整数数组 nums 。
分区 是指将数组按照下标 i （0 <= i < n - 1）划分成两个 非空 子数组，其中：
- 左子数组包含区间
[0, i]内的所有下标。 - 右子数组包含区间
[i + 1, n - 1]内的所有下标。
对左子数组和右子数组先求元素 和 再做 差 ，统计并返回差值为 偶数 的 分区 方案数。
示例 1：
输入：nums = [10,10,3,7,6]
输出：4
解释：
共有 4 个满足题意的分区方案：
[10]、[10, 3, 7, 6]元素和的差值为10 - 26 = -16，是偶数。[10, 10]、[3, 7, 6]元素和的差值为20 - 16 = 4，是偶数。[10, 10, 3]、[7, 6]元素和的差值为23 - 13 = 10，是偶数。[10, 10, 3, 7]、[6]元素和的差值为30 - 6 = 24，是偶数。
示例 2：
输入：nums = [1,2,2]
输出：0
解释：
不存在元素和的差值为偶数的分区方案。
示例 3：
输入：nums = [2,4,6,8]
输出：3
解释：
所有分区方案都满足元素和的差值为偶数。
提示：
2 <= n == nums.length <= 1001 <= nums[i] <= 100
解题思路
方法一：前缀和
我们用两个变量 和 分别表示左子数组和右子数组的和，初始时 ，而 。
接下来，我们遍历前 个元素，每次将当前元素加到左子数组中，同时从右子数组中减去当前元素，然后判断 是否为偶数，如果是则答案加一。
最后返回答案即可。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def countPartitions(self, nums: List[int]) -> int:
l, r = 0, sum(nums)
ans = 0
for x in nums[:-1]:
l += x
r -= x
ans += (l - r) % 2 == 0
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on efficient sum calculation and parity checking to avoid unnecessary recomputations.
- question_mark
Be cautious of using brute-force methods that lead to high time complexity.
- question_mark
Look for optimized ways to track the parity of subarray sums to minimize redundant work.
常见陷阱
外企场景- error
Ignoring the parity of prefix sums and recalculating sums for each partition.
- error
Not leveraging prefix sum and parity, resulting in a brute-force O(n^2) solution.
- error
Overlooking edge cases where partitions result in no valid even sum differences.
进阶变体
外企场景- arrow_right_alt
Optimize further for larger arrays by focusing on parity without storing full sums.
- arrow_right_alt
Explore dynamic programming alternatives for this problem if required by the interviewer.
- arrow_right_alt
Consider modifying the problem to track odd sum differences or another mathematical property.