今日题目

3432. Count Partitions with Even Sum Difference

解题思路

本题要求将数组划分为两部分，且这两部分之和的差为偶数。

要使差为偶数，两部分的和对 2 取模的结果必须相同，即两部分的和同为偶数或同为奇数。因此，整个数组的总和必须是偶数。

反过来说，若数组总和为偶数，则无论如何划分，两部分之和对 2 取模的结果必然相同。否则，数组总和将为奇数，不存在满足条件的划分。

由此得出结论：当数组总和为奇数时，答案为 0；当数组总和为偶数时，答案为 $n-1$。

解题方法

当数组总和为奇数时返回 0，为偶数时返回 $n-1$。

复杂度分析

• 时间复杂度：

$O(n)$，其中 n 为数组长度。

• 空间复杂度：

$O(n)$，其中 n 为数组长度。

代码

class Solution:
    def countPartitions(self, nums: List[int]) -> int:
        if sum(nums) % 2 == 1:
            return 0
        return len(nums) - 1