How can I solve the 'Number of Sub-arrays With Odd Sum' problem?

Use dynamic programming with prefix sums to track the cumulative sum and count the odd and even subarrays efficiently.

What is the optimal time complexity for this problem?

The optimal time complexity is O(n), where n is the length of the array.

Why is the modulo 10^9 + 7 used in this problem?

It is used to prevent overflow by keeping the result within manageable limits.

What is the key pattern used in this problem?

The key pattern is state transition dynamic programming, specifically using prefix sums and parity tracking.

What are some common pitfalls when solving this problem?

Common pitfalls include incorrect updates of the odd/even sum counts, failing to use modulo operations, and overcomplicating the solution.

#1524

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

和为奇数的子数组数目

给你一个整数数组 arr 。请你返回和为奇数的子数组数目。由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。示例 1：输入： arr = [1,3,5] 输出： 4 解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。所有子数组的和…

数组数学动态规划前缀和

题目描述

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

lightbulb

解题思路

方法一：前缀和 + 计数器

我们定义一个长度为 $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

11

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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidate shows familiarity with prefix sum techniques.
question_mark
Candidate demonstrates understanding of dynamic programming state transitions.
question_mark
Candidate correctly applies modulo operations to manage large numbers.

warning

常见陷阱

外企场景

error
Incorrectly updating the odd/even sum counts, leading to wrong results.
error
Overcomplicating the problem by attempting a brute-force solution with nested loops.
error
Failing to apply modulo 10^9 + 7, causing overflow issues.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to return subarrays with even sums.
arrow_right_alt
Adapt the problem to count subarrays with sums divisible by a given number.
arrow_right_alt
Consider variations with different data types (e.g., floating-point numbers).

help

常见问题

外企场景

继续练习

#1872 石子游戏 VIII #1140 石子游戏 II #1563 石子游戏 V