LEETCODE 1524. Number of Sub-arrays With Odd Sum 解题思路分析

题目大意：

和为奇数的子数组数目

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1524

解题思路分析：

这道题使用前缀和来解题非常简便。我们之前的文章多次讲过前缀和的使用方式，这里再简单介绍一下，f(i)代表从下标0累加至下标i的和。如果我们想知道数组中任意子区间x到y的数字和，那么：sum(x, y)=f(y)-f(x-1)。

回到本题，我们从数组首位向后求出每一位上的前缀和。然后再使用2个变量保存奇数前缀和的个数oddNum，以及偶数前缀和的个数evenNum。解题时，如果当前前缀和为奇数，那么oddNum加一，因为当前前缀区间为一个合理区间，因此返回结果加一。接下来是关键，由于当前的前缀和为奇数，那么在已遍历过的前缀和中如果存在偶数前缀和，那么当前前缀区间与那些偶数前缀区间的差必定是奇数区间。此时返回结果须累加偶数前缀和的个数。比如：当前区间[0, 10]的前缀和为奇数，另外我们已知有2个前缀和区间[0, 3]和[0, 6]是偶数，那么区间[4, 10]与[7, 10]之和必定是奇数。 解题时我们不必关心具体哪些前缀区间和为奇数或者偶数，只需要知道他们的个数即可。

反之同理，如果当前前缀和为偶数，那么evenNum个数加一。同时将奇数前缀和的个数累加至返回结果即可。

实现代码：

public int numOfSubarrays(int[] arr) {
    int oddNum=0, evenNum=0; // 奇数前缀和个数，偶数前缀和个数
    int preSum=0; // 前缀和
    int res=0; // 返回结果
    for(int num : arr){ // 循环每个数
        preSum+=num; // 计算前缀和
        if(preSum%2==0){ // 前缀和是偶数
            evenNum++; // 偶数前缀和个数加一
            res+=oddNum; // 将奇数前缀和个数累加至返回结果
        }else{ // 前缀和是奇数
            oddNum++; // 奇数前缀和个数加一
            res++; // 返回结果加一（当前前缀区间）
            res+=evenNum; // 将偶数前缀和个数累加至返回结果
        }
        res%=1000000007;
    }
    return res;
}

本题解法执行时间为13ms。

Runtime: 13 ms, faster than 66.40% of Java online submissions for Number of Sub-arrays With Odd Sum.

Memory Usage: 116.3 MB, less than 32.02% of Java online submissions for Number of Sub-arrays With Odd Sum.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1524-number-of-sub-arrays-with-odd-sum-解题思路分析/