Easy

题目描述

给你一个长度为 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

解题思路

这道题的关键洞察是：两个数的差值为偶数，当且仅当这两个数的奇偶性相同（都是奇数或都是偶数）。

因此我们可以通过以下数学推导来简化问题：

  • 设左子数组和为 leftSum，右子数组和为 rightSum
  • 总和 totalSum = leftSum + rightSum
  • 差值 diff = leftSum - rightSum = leftSum - (totalSum - leftSum) = 2 * leftSum - totalSum

要使差值为偶数，需要 2 * leftSum - totalSum 为偶数。由于 2 * leftSum 总是偶数，所以需要 totalSum 也为偶数。

关键发现：如果总和为奇数，则不存在任何有效分割；如果总和为偶数，则所有分割都有效。

这是因为当总和为偶数时，对于任意分割点，左子数组和与右子数组和的奇偶性必然相同，它们的差值就是偶数。

算法步骤：

  1. 计算数组总和
  2. 如果总和为奇数，返回 0
  3. 如果总和为偶数，返回 n-1（即所有可能的分割数）

时间复杂度：O(n)，空间复杂度：O(1)。

代码实现

class Solution {
public:
    int countPartitions(vector<int>& nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        // 如果总和为奇数，不存在有效分割
        if (totalSum % 2 == 1) {
            return 0;
        }
        
        // 如果总和为偶数，所有分割都有效
        return nums.size() - 1;
    }
};

class Solution:
    def countPartitions(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        
        # 如果总和为奇数，不存在有效分割
        if total_sum % 2 == 1:
            return 0
        
        # 如果总和为偶数，所有分割都有效
        return len(nums) - 1

public class Solution {
    public int CountPartitions(int[] nums) {
        int totalSum = nums.Sum();
        
        // 如果总和为奇数，不存在有效分割
        if (totalSum % 2 == 1) {
            return 0;
        }
        
        // 如果总和为偶数，所有分割都有效
        return nums.Length - 1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var countPartitions = function(nums) {
    const n = nums.length;
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    
    let leftSum = 0;
    let count = 0;
    
    for (let i = 0; i < n - 1; i++) {
        leftSum += nums[i];
        const rightSum = totalSum - leftSum;
        const diff = leftSum - rightSum;
        
        if (diff % 2 === 0) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(n)需要遍历一次数组计算总和
空间复杂度O(1)只使用常数额外空间