使用 C++ 查找具有 m 个奇数的子数组的数量
如果您曾经使用过C++，那么您必须知道子数组是什么以及它们有多大用处。众所周知，在C++中，我们可以轻松解决多个数学问题。因此，在本文中，我们将解释有关如何借助C++中的这些子数组找到M个奇数的完整信息。
在这个问题中，我们需要找到许多由给定数组和整数m组成的子数组，其中每个子数组都包含恰好m个奇数。所以这是这种方法的简单示例-
Input : array = { 6,3,5,8,9 }, m = 2
Output : 5
Explanation : Subarrays with exactly 2 odd numbers are
{ 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 }
Input : array = { 1,6,3,2,5,4 }, m = 2
Output : 6
Explanation : Subarrays with exactly 2 odd numbers are
{ 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，为找到的每个子数组增加结果计数器计数，最后打印存储在计数变量中的结果。
第二种方法
另一种方法是创建一个数组，用于存储具有“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计数以保持可能子数组的计数，用0计算奇数，用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时，可以形成子数组的数量直到索引。
最后，我们打印多个子数组，其中m个奇数存储在count变量中并获得输出。
结论
在本文中，我们了解了从两种方法中找到具有m个奇数的子数组数量的方法-
生成每个子数组并检查其中的m个奇数，并为找到的每个子数组增加计数。这段代码的时间复杂度是O(n2)。
高效的方法，它遍历数组的每个元素并创建一个前缀数组，并在前缀数组的帮助下找到结果。这段代码的时间复杂度是O(n)。
希望您发现这篇文章有助于理解问题和解决方案。