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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。