3432. 统计元素和差值为偶数的分区方案
题目描述
给你一个长度为 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
解法
方法一：前缀和
我们用两个变量 $l$ 和 $r$ 分别表示左子数组和右子数组的和，初始时 $l = 0$，而 $r = \sum_{i=0}^{n-1} \textit{nums}[i]$。
接下来，我们遍历前 $n - 1$ 个元素，每次将当前元素加到左子数组中，同时从右子数组中减去当前元素，然后判断 $l - r$ 是否为偶数，如果是则答案加一。
最后返回答案即可。
时间复杂度 $O(n)$，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。
Python3
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
Java
class Solution {
public int countPartitions(int[] nums) {
int l = 0, r = 0;
for (int x : nums) {
r += x;
}
int ans = 0;
for (int i = 0; i < nums.length - 1; ++i) {
l += nums[i];
r -= nums[i];
if ((l - r) % 2 == 0) {
++ans;
}
}
return ans;
}
}
C++
class Solution {
public:
int countPartitions(vector<int>& nums) {
int l = 0, r = accumulate(nums.begin(), nums.end(), 0);
int ans = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
l += nums[i];
r -= nums[i];
if ((l - r) % 2 == 0) {
++ans;
}
}
return ans;
}
};
Go
func countPartitions(nums []int) (ans int) {
l, r := 0, 0
for _, x := range nums {
r += x
}
for _, x := range nums[:len(nums)-1] {
l += x
r -= x
if (l-r)%2 == 0 {
ans++
}
}
return
}
TypeScript
function countPartitions(nums: number[]): number {
let l = 0;
let r = nums.reduce((a, b) => a + b, 0);
let ans = 0;
for (const x of nums.slice(0, -1)) {
l += x;
r -= x;
ans += (l - r) % 2 === 0 ? 1 : 0;
}
return ans;
}