题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个整数数组，要求这个数组中所有子数组中和为奇数的数目。

思路分享

  • 前缀和的思路，可以参考 【Leetcode Daily】303区域和检索-数组不可变

  • 虽然是陆爻齐自己思考了出来，但如果没有提前知道是前缀和区域，应该是做不出来的。

  • 回忆解题的过程，就是思考如何快速判定奇数区域时，对做了前缀和了数组观察偶然发现，只要记录此前的奇数和偶数的数目，就能方便地计算现有的数字与此前数字之前区域的和为奇数的数目。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        s = list(accumulate(arr, initial=0))
        even_num = 0
        odd_num = 0
        ans = 0
        for i in s:
            if i%2 == 0:
                ans += odd_num
                even_num += 1
            else:
                ans += even_num
                odd_num += 1

        return ans % (1_000_000_000+7)