leetcode前缀和(1524. 和为奇数的子数组数目)

媒介

颠末前期的底子训练以及部分实战练习，粗略把握了各种题型的解题思绪。现阶段开始专项练习。
描述

   给你一个整数数组 arr 。请你返回和为 奇数 的子数组数目。
  由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。
  
  示例 1：

1. <strong>输入：</strong>arr = [1,3,5]
2. <strong>输出：</strong>4
3. <strong>解释：</strong>所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。
4. 所有子数组的和为 [1,4,9,3,8,5].
5. 奇数和包括 [1,9,3,5] ，所以答案为 4 。

复制代码

示例 2 ：

1. <strong>输入：</strong>arr = [2,4,6]
2. <strong>输出：</strong>0
3. <strong>解释：</strong>所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。
4. 所有子数组和为 [2,6,12,4,10,6] 。
5. 所有子数组和都是偶数，所以答案为 0 。

复制代码

示例 3：

1. <strong>输入：</strong>arr = [1,2,3,4,5,6,7]
2. <strong>输出：</strong>16

复制代码

示例 4：

1. <strong>输入：</strong>arr = [100,100,99,99]
2. <strong>输出：</strong>4

复制代码

示例 5：

1. <strong>输入：</strong>arr = [7]
2. <strong>输出：</strong>1

复制代码

  提示：
  

• 1 <= arr.length <= 10^5
  
• 1 <= arr <= 100
  

  实现原理与步骤

1.累加和为偶数，减去前序累加和为奇数的情况，剩余的为奇数。在盘算个数情况下便是前序的奇数个数。
2.累加和为奇数，减去前序累加和为偶数的情况，剩余的为偶数。在盘算个数情况下便是前序的偶数个数。
3.初始化odd为0，even为1.1代表[]空偶值情况。
4.之前思量此方法是否会存在重复情况，由于累加和持续随数字位置递增，剩余的尾数不断在更新则不会出现重复情况。
 实现代码

1. class Solution {
2.     private static final int MODULO = 1000000007;
4.     public int numOfSubarrays(int[] arr) {
5.         int odd = 0, even = 1;
6.         int res = 0;
7.         int sum = 0;
8.         int length = arr.length;
9.         for (int i = 0; i < length; i++) {
10.             sum += arr[i];
11.             res = (res + (sum % 2 == 0 ? odd : even)) % MODULO;
12.             if (sum % 2 == 0) {
13.                 even++;
14.             } else {
15.                 odd++;
16.             }
17.         }
18.         return res;
19.     }
20. }

复制代码

1.QA:


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。