1524. 和为奇数的子数组数目

🟠   🔖  数组 数学 动态规划 前缀和  🔗 力扣 LeetCode

题目

Given an array of integers arr, return the number of subarrays with anodd sum.

Since the answer can be very large, return it modulo 109 + 7.

Example 1:

Input: arr = [1,3,5]

Output: 4

Explanation: All subarrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]

All sub-arrays sum are [1,4,9,3,8,5].

Odd sums are [1,9,3,5] so the answer is 4.

Example 2:

Input: arr = [2,4,6]

Output: 0

Explanation: All subarrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]

All sub-arrays sum are [2,6,12,4,10,6].

All sub-arrays have even sum and the answer is 0.

Example 3:

Input: arr = [1,2,3,4,5,6,7]

Output: 16

Constraints:

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

题目大意

给你一个整数数组 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

示例 4：

输入： arr = [100,100,99,99]

输出： 4

示例 5：

输入： arr = [7]

输出： 1

提示：

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

解题思路

1. 前缀和思想：

   • 设 prefixSum[i] 为 arr[0] 到 arr[i] 的前缀和。
   • 若 prefixSum[j] - prefixSum[i] 为 奇数，则 prefixSum[j] 和 prefixSum[i] 必须是 一奇一偶。

2. 维护前缀奇偶计数：

   • 设 oddCount 表示前缀和为 奇数 的个数。
   • 设 evenCount 表示前缀和为 偶数 的个数。
   • 遍历 arr，更新 sum（前缀和）：
     • 若 sum 为 奇数：
       • 奇数 - 偶数 = 奇数，即 sum - evenSum 构成奇数子数组。
       • result += evenCount + 1（包括子数组只有 arr[i] 一个元素的情况）。
       • oddCount++。
     • 若 sum 为 偶数：
       • 偶数 - 奇数 = 奇数，即 sum - oddSum 构成奇数子数组。
       • result += oddCount。
       • evenCount++。

3. 取模：

   • 由于答案可能过大，每次更新 result 时都进行 mod = 10^9 + 7 取模。

复杂度分析

• 时间复杂度：O(n)，遍历数组一次。
• 空间复杂度：O(1)，仅使用常数级变量。

代码

/**
 * @param {number[]} arr
 * @return {number}
 */
var numOfSubarrays = function (arr) {
	const mod = Math.pow(10, 9) + 7;
	let oddCount = 0;
	let evenCount = 0;
	let result = 0;
	let sum = 0;
	for (let i = 1; i <= arr.length; i++) {
		sum += arr[i - 1];
		if (sum % 2 == 1) {
			oddCount++;
			result = (result + evenCount + 1) % mod;
		} else {
			evenCount++;
			result = (result + oddCount) % mod;
		}
	}
	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
2098	长度为 K 的最大偶数和子序列 🔒		贪心 数组 排序	🟠	🀄️ 🔗