class Solution {
public:
int numOfSubarrays(vector<int>& arr) {
}
};
1524. 和为奇数的子数组数目
给你一个整数数组 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^51 <= arr[i] <= 100原站题解
golang 解法, 执行用时: 120 ms, 内存消耗: 7.7 MB, 提交时间: 2023-09-28 23:40:53
func numOfSubarrays(arr []int) int {
sum, ans, odd, even := 0, 0, 0, 1
for _, num := range arr {
sum += num
if (sum & 1) == 1 {
ans += even
odd++
} else {
ans += odd
even++
}
}
return ans%1000000007
}
java 解法, 执行用时: 3 ms, 内存消耗: 52.9 MB, 提交时间: 2023-09-28 23:40:40
class Solution {
public int numOfSubarrays(int[] arr) {
int[] s = new int[]{1, 0};
long r = 0;
for (int i = 0, sum = 0; i < arr.length; i++) {
++s[sum ^= arr[i] & 1];
r += s[sum ^ 1];
}
return (int )(r % 1000000007);
}
}
cpp 解法, 执行用时: 112 ms, 内存消耗: 105.9 MB, 提交时间: 2023-09-28 23:40:18
class Solution {
public:
int numOfSubarrays(vector<int>& arr) {
int m = arr.size();
const int INF = 1e9 + 7;
int ans = 0;
int even = 1 - arr[0] % 2; //以arr[0]结尾的和为偶数的子数组个数
int next_even = 0;
int odd = arr[0] % 2; //以arr[0]结尾的和为奇数的子数组个数
int next_odd = 0;
ans += odd;
for (int i = 1; i < m; ++i) {
if (arr[i] % 2) { //如果该数字为奇数
next_even = odd; //以arr[i]结尾的和为偶数的子数组个数
next_odd = even + 1; //以arr[i]结尾的和为奇数的子数组个数
}
else {
next_even = even + 1; //以arr[i]结尾的和为偶数的子数组个数
next_odd = odd; //以arr[i]结尾的和为奇数的子数组个数
}
ans += next_odd;
ans %= INF;
odd = next_odd; //覆盖状态
even = next_even; //覆盖状态
}
return ans;
}
};
python3 解法, 执行用时: 152 ms, 内存消耗: 20.3 MB, 提交时间: 2023-09-28 23:40:00
class Solution:
def numOfSubarrays(self, arr: List[int]) -> int:
MODULO = 10**9 + 7
odd, even = 0, 1
subarrays = 0
total = 0
for x in arr:
total += x
subarrays += (odd if total % 2 == 0 else even)
if total % 2 == 0:
even += 1
else:
odd += 1
return subarrays % MODULO
cpp 解法, 执行用时: 124 ms, 内存消耗: 105.8 MB, 提交时间: 2023-09-28 23:39:45
class Solution {
public:
int numOfSubarrays(vector<int>& arr) {
const int MODULO = 1000000007;
int odd = 0, even = 1;
int subarrays = 0;
int sum = 0;
int length = arr.size();
for (int i = 0; i < length; i++) {
sum += arr[i];
subarrays = (subarrays + (sum % 2 == 0 ? odd : even)) % MODULO;
if (sum % 2 == 0) {
even++;
} else {
odd++;
}
}
return subarrays;
}
};
java 解法, 执行用时: 8 ms, 内存消耗: 55.2 MB, 提交时间: 2023-09-28 23:39:35
class Solution {
public int numOfSubarrays(int[] arr) {
final int MODULO = 1000000007;
int odd = 0, even = 1;
int subarrays = 0;
int sum = 0;
int length = arr.length;
for (int i = 0; i < length; i++) {
sum += arr[i];
subarrays = (subarrays + (sum % 2 == 0 ? odd : even)) % MODULO;
if (sum % 2 == 0) {
even++;
} else {
odd++;
}
}
return subarrays;
}
}