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++GoTypeScriptRust

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

impl Solution {
    pub fn count_partitions(nums: Vec<i32>) -> i32 {
        let mut l: i64 = 0;
        let mut r: i64 = nums.iter().map(|&x| x as i64).sum();
        let mut ans: i32 = 0;

        for &x in nums[..nums.len() - 1].iter() {
            l += x as i64;
            r -= x as i64;
            if (l - r) % 2 == 0 {
                ans += 1;
            }
        }

        ans
    }
}

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

题目描述

解法

方法一：前缀和

评论