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 <= 100
1 <= 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)$。

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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;
}

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

题目描述

解法

方法一：前缀和

评论