使用 C++ 查找包含 m 个奇数的子数组的数量
如果您曾经使用过 C++，您一定知道子数组是什么以及它们有多有用。众所周知，在 C++ 中，我们可以轻松解决多个数学问题。因此，在本文中，我们将解释如何在 C++ 中借助这些子数组找到 M 个奇数的完整信息。
在这个问题中，我们需要找到由给定数组和整数 m 形成的许多子数组，其中每个子数组恰好包含 m 个奇数。因此，这是此方法的简单示例 −
输入:数组 = { 6,3,5,8,9 }, m = 2
输出:5
解释:恰好具有 2 个奇数的子数组是
{ 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 }
输入:数组 = { 1,6,3,2,5,4 }, m = 2
输出:6
解释:恰好具有 2 个奇数的子数组是
{ 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 }
第一种方法
在此方法中，从给定数组生成所有可能的子数组，并检查每个子数组是否恰好有 m 个奇数。这是一种简单的生成和查找方法，此方法的时间复杂度为 O(n2)。
示例
#include <bits/stdc++.h>
using namespace std;
int main (){
int a[] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0; // n 是数组的大小，m 个数字需要在子数组中找到，
// count 是包含 m 个奇数的子数组的数量
for (int i = 0; i < n; i++){ // 外循环处理每个元素。
int odd = 0;
for (int j = i; j < n; j++) {// 内循环查找包含 m 个数字的子数组
if (a[j] % 2)
odd++;
if (odd == m) // 如果奇数等于 m。
count++;
}
}
cout << "n个数字的子数组数量为:" << count;
return 0;
}
输出
n个数字的子数组数量为:6
上述代码的解释
在此代码中，我们使用嵌套循环来查找具有 m 个奇数的子数组，并且外循环用于增加"i"，这将用于处理数组中的每个元素。
内循环用于查找子数组并处理元素，直到奇数计数器达到 m，增加找到的每个子数组的结果计数器计数，最后打印存储在 count 变量中的结果。
第二种方法
另一种方法是创建一个数组来存储带有"i"的前缀的数量奇数，处理每个元素，并对找到的每个奇数增加奇数的数量。
当奇数的数量超过或等于m时，将前缀数组中 (odd - m ) 位置的数字相加。
当 odd 大于或等于 m 时，我们计算形成的子数组的数量，直到索引和"odd - m"数字添加到 count 变量中。处理完每个元素后，结果存储在 count 变量中。
示例
#include <bits/stdc++.h>
using namespace std;
int main (){
int array[ ] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0, odd = 0, i;
int prefix_array[n + 1] = { 0 };
// 外循环处理数组的每个元素
for (i = 0; i < n; i++){
prefix_array[odd] = prefix_array[odd] + 1; // 在 prefix_array[ ] 中的奇数索引处实现值
// 如果数组元素为奇数，则增加奇数变量
if (array[i] % 2 == 0)
odd++;
// 如果奇数元素的数量等于或大于 m
// 然后找到可以形成到索引的可能子数组的数量。
if (odd >= m)
count += prefix_array[odd - m];
}
cout << "具有 n 个数字的子数组的数量为:" << count;
return 0;
}
输出
n 个数字的子数组数量为:6
上述代码的解释
使用起始值 − 初始化数组和变量
int array[ 6 ] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0, odd = 0, i;
int prefix_array[n + 1] = { 0 };
在此，我们用数组的大小初始化变量 n，用要查找的奇数数量初始化 m，用 0 初始化 count 以保持可能子数组的数量，用 0 初始化 odd，用 0 初始化大小为 n + 1 的 prefix_array。
理解循环
for (i = 0; i < n; i++){
prefix_array[odd] = prefix_array[odd] + 1;
if (array[i] % 2 == 0)
odd++;
if (odd >= m)
count += prefix_array[odd - m];
}
在此循环中，我们在 prefix_array[ ] 中的奇数索引处实现值，然后如果找到奇数，则递增奇数变量。我们发现当奇数变量等于或大于 m 时，可以形成直到索引的子数组的数量。
最后，我们打印存储在 count 变量中的具有 m 个奇数的子数组的数量并获取输出。
结论
在本文中，我们从两种方法中了解了查找具有 m 个奇数的子数组数量的方法 −
生成每个子数组并检查其中的 m 个奇数，并为找到的每个子数组递增计数。此代码的时间复杂度为 O(n2)。
高效方法，即遍历数组的每个元素并创建前缀数组，然后借助前缀数组找到结果。此代码的时间复杂度为 O(n)。
希望本文有助于您理解问题和解决方案。
