Medium

题目描述

给你一个整数数组 arr，请返回所有和为奇数的子数组数目。

由于答案可能会很大，请返回答案对 10^9 + 7 取余的结果。

示例 1：

输入：arr = [1,3,5]
输出：4
解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]]
所有子数组的和为 [1,4,9,3,8,5]
奇数和为 [1,9,3,5]，所以答案为 4

示例 2：

输入：arr = [2,4,6]
输出：0
解释：所有的子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]]
所有子数组的和为 [2,6,12,4,10,6]
所有子数组的和都是偶数，答案为 0

示例 3：

输入：arr = [1,2,3,4,5,6,7]
输出：16

提示：

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 100

解题思路

这道题可以使用前缀和的思想来解决。关键观察是：一个子数组的和为奇数，当且仅当该子数组的起始位置和结束位置的前缀和奇偶性不同。

具体思路：

  1. 遍历数组，维护前缀和
  2. 用两个变量 even 和 odd 分别记录前缀和为偶数和奇数的位置数量
  3. 对于当前位置 i，如果前缀和为奇数，那么以位置 i 结尾的奇数和子数组个数等于之前所有前缀和为偶数的位置数量（包括位置 -1，即空前缀）
  4. 如果前缀和为偶数，那么以位置 i 结尾的奇数和子数组个数等于之前所有前缀和为奇数的位置数量

初始时 even = 1（表示空前缀和为 0，是偶数），odd = 0。

时间复杂度：O(n)，只需要遍历一次数组 空间复杂度：O(1)，只使用常数个变量

这种方法避免了暴力枚举所有子数组，是最优解。

代码实现

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int even = 1, odd = 0; // 偶数和奇数前缀和的个数
        int prefixSum = 0;
        int result = 0;
        
        for (int num : arr) {
            prefixSum += num;
            if (prefixSum % 2 == 0) {
                result = (result + odd) % MOD;
                even++;
            } else {
                result = (result + even) % MOD;
                odd++;
            }
        }
        
        return result;
    }
};

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        even, odd = 1, 0  # 偶数和奇数前缀和的个数
        prefix_sum = 0
        result = 0
        
        for num in arr:
            prefix_sum += num
            if prefix_sum % 2 == 0:
                result = (result + odd) % MOD
                even += 1
            else:
                result = (result + even) % MOD
                odd += 1
        
        return result

public class Solution {
    public int NumOfSubarrays(int[] arr) {
        const int MOD = 1000000007;
        int even = 1, odd = 0; // 偶数和奇数前缀和的个数
        int prefixSum = 0;
        int result = 0;
        
        foreach (int num in arr) {
            prefixSum += num;
            if (prefixSum % 2 == 0) {
                result = (result + odd) % MOD;
                even++;
            } else {
                result = (result + even) % MOD;
                odd++;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} arr
 * @return {number}
 */
var numOfSubarrays = function(arr) {
    const MOD = 1000000007;
    let oddCount = 0;
    let evenCount = 1;
    let result = 0;
    let sum = 0;
    
    for (let num of arr) {
        sum += num;
        if (sum % 2 === 0) {
            result = (result + oddCount) % MOD;
            evenCount++;
        } else {
            result = (result + evenCount) % MOD;
            oddCount++;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大O表示法
时间复杂度O(n)
空间复杂度O(1)

相关题目