comments	difficulty	edit_url	tags
true	简单	https://github.com/doocs/leetcode/edit/main/solution/3400-3499/3432.Count%20Partitions%20with%20Even%20Sum%20Difference/README.md	数组 数学 前缀和

3432. 统计元素和差值为偶数的分区方案

English Version

题目描述

给你一个长度为 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 <= 100
• 1 <= nums[i] <= 100

解法

方法一：前缀和

我们用两个变量 $l$ 和 $r$ 分别表示左子数组和右子数组的和，初始时 $l=0$，而 $r=\sum _{i=0}^{n-1}\mathit{\text{nums}}[i]$。

接下来，我们遍历前 $n-1$ 个元素，每次将当前元素加到左子数组中，同时从右子数组中减去当前元素，然后判断 $l-r$ 是否为偶数，如果是则答案加一。

最后返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\mathit{\text{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;
}