原文链接: https://leetcode-cn.com/problems/number-of-sub-arrays-with-odd-sum

英文原文

Given an array of integers arr, return the number of subarrays with an odd 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 <= 105
• 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

通过代码

高赞题解

一直刷简单题的小菜鸡竞赛居然灵光乍现做出了这题
统计一下前缀和中有几个奇数几个偶数，答案其实就是 奇数的个数×偶数的个数+奇数的个数

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        sums = [0]
        odd = 0
        even = 0
        for i in range(len(arr)):
            sums.append(sums[-1] + arr[i])
            if sums[-1] % 2 == 0:
                even += 1
            else:
                odd += 1
        return int((odd + odd*even) % (1e9+7))

从前缀和里随意选出两个数做差，差值就是子数组的和，当选出的两个数是一个奇数一个偶数时，
子数组的和是奇数，所以这样的选法一共有 奇数的个数×偶数的个数 这么多种

统计信息

通过次数	提交次数	AC比率
5451	12564	43.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言