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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

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

方法一：前缀和 + 数学

这道题要求返回和为奇数的子数组数目。为了快速计算任意子数组的和，可以通过维护前缀和的方式。这道题只需要知道每个子数组的和的奇偶性，不需要知道子数组的和的具体值，因此不需要维护每一个前缀和，只需要维护奇数前缀和的数量与偶数前缀和的数量。

分别使用 odd 和 even 表示奇数前缀和的数量与偶数前缀和的数量。初始时，odd}=0，even}=1，因为空的前缀的和是 0，也是偶数前缀和。

遍历数组 arr 并计算前缀和。对于下标 i 的位置的前缀和（即 arr}[0]+\textit{arr}[1]+\ldots+\textit{arr}[i]），根据奇偶性进行如下操作：

  • 当下标 i 的位置的前缀和是偶数时，如果下标 j 满足 j < i 且下标 j 的位置的前缀和是奇数，则从下标 j+1 到下标 i 的子数组的和是奇数，因此，以下标 i 结尾的子数组中，和为奇数的子数组的数量即为奇数前缀和的数量 odd；

  • 当下标 i 的位置的前缀和是奇数时，如果下标 j 满足 j < i 且下标 j 的位置的前缀和是偶数，则从下标 j+1 到下标 i 的子数组的和是奇数，因此，以下标 i 结尾的子数组中，和为奇数的子数组的数量即为偶数前缀和的数量 even。

上述下标 j 的最小可能取值为 -1，当 j=-1 时表示下标 j 的位置的前缀为空。

在更新和为奇数的子数组数量之后，需要根据下标 i 的位置的前缀和的奇偶性更新 odd 或 even 的值。如果前缀和是奇数，则 odd 的值加 1；如果前缀和是偶数，则 even 的值加 1。

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numOfSubarrays(int[] arr) {
        final int MODULO = 1000000007;
        int odd = 0, even = 1;
        int subarrays = 0;
        int sum = 0;
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            sum += arr[i];
            subarrays = (subarrays + (sum % 2 == 0 ? odd : even)) % MODULO;
            if (sum % 2 == 0) {
                even++;
            } else {
                odd++;
            }
        }
        return subarrays;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        const int MODULO = 1000000007;
        int odd = 0, even = 1;
        int subarrays = 0;
        int sum = 0;
        int length = arr.size();
        for (int i = 0; i < length; i++) {
            sum += arr[i];
            subarrays = (subarrays + (sum % 2 == 0 ? odd : even)) % MODULO;
            if (sum % 2 == 0) {
                even++;
            } else {
                odd++;
            }
        }
        return subarrays;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MODULO = 10**9 + 7
        odd, even = 0, 1
        subarrays = 0
        total = 0
        
        for x in arr:
            total += x
            subarrays += (odd if total % 2 == 0 else even)
            if total % 2 == 0:
                even += 1
            else:
                odd += 1
        
        return subarrays % MODULO

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 arr 的长度。遍历数组一次，对于数组中的每个元素，更新前缀和、和为奇数的子数组数目以及 odd 和 even 的值的时间复杂度都是 O(1)，因此总时间复杂度是 O(n)。

  • 空间复杂度：O(1)。只需要维护常量的额外空间。

 Comments
On this page
1524-和为奇数的子数组数目