跳转至

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

题目描述

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

解法

方法一：前缀和 + 计数器

思考

统计子数组和为奇数的个数。子数组有 \(O(n^2)\) 个，\(n\le 10^5\)，直接求和不可行。子数组和的奇偶等于两端前缀和之差的奇偶。

前缀和为奇当且仅当此前偶数前缀的个数可与之配对（奇减偶为奇），偶前缀则与已有奇前缀配对。扫描时维护奇、偶前缀计数，每走一步按当前前缀奇偶累加配对并更新计数，最后对 \(10^9+7\) 取模。

我们定义一个长度为 \(2\) 的数组 \(\textit{cnt}\) 作为计数器，其中 \(\textit{cnt}[0]\) 和 \(\textit{cnt}[1]\) 分别表示前缀和为偶数和奇数的子数组的个数。初始时 \(\textit{cnt}[0] = 1\)，而 \(\textit{cnt}[1] = 0\)。

接下来，我们维护当前的前缀和 \(s\)，初始时 \(s = 0\)。

遍历数组 \(\textit{arr}\)，对于遍历到的每个元素 \(x\)，我们将 \(s\) 的值加上 \(x\)，然后根据 \(s\) 的奇偶性，将 \(\textit{cnt}[s \mod 2 \oplus 1]\) 的值累加到答案中，然后我们将 \(\textit{cnt}[s \mod 2]\) 的值加 \(1\)。

遍历结束后，我们即可得到答案。注意答案的取模运算。

时间复杂度 \(O(n)\)，其中 \(n\) 为数组 \(\textit{arr}\) 的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        cnt = [1, 0]
        ans = s = 0
        for x in arr:
            s += x
            ans = (ans + cnt[s & 1 ^ 1]) % mod
            cnt[s & 1] += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int numOfSubarrays(int[] arr) {
        final int mod = (int) 1e9 + 7;
        int[] cnt = {1, 0};
        int ans = 0, s = 0;
        for (int x : arr) {
            s += x;
            ans = (ans + cnt[s & 1 ^ 1]) % mod;
            ++cnt[s & 1];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        const int mod = 1e9 + 7;
        int cnt[2] = {1, 0};
        int ans = 0, s = 0;
        for (int x : arr) {
            s += x;
            ans = (ans + cnt[s & 1 ^ 1]) % mod;
            ++cnt[s & 1];
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func numOfSubarrays(arr []int) (ans int) {
    const mod int = 1e9 + 7
    cnt := [2]int{1, 0}
    s := 0
    for _, x := range arr {
        s += x
        ans = (ans + cnt[s&1^1]) % mod
        cnt[s&1]++
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function numOfSubarrays(arr: number[]): number {
    let ans = 0;
    let s = 0;
    const cnt: number[] = [1, 0];
    const mod = 1e9 + 7;
    for (const x of arr) {
        s += x;
        ans = (ans + cnt[(s & 1) ^ 1]) % mod;
        cnt[s & 1]++;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn num_of_subarrays(arr: Vec<i32>) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let mut cnt = [1, 0];
        let mut ans = 0;
        let mut s = 0;
        for &x in arr.iter() {
            s += x;
            ans = (ans + cnt[((s & 1) ^ 1) as usize]) % MOD;
            cnt[(s & 1) as usize] += 1;
        }
        ans
    }
}

评论