使用 C++ 查找奇数和子数组的数量
子数组是数组的连续部分。例如，我们考虑一个数组 [5, 6, 7, 8]，那么有十个非空子数组，如 (5)、(6)、(7)、(8)、(5, 6)、(6,7)、(7,8)、(5,6,7)、(6,7,8) 和 (5,6,7,8)。
在本指南中，我们将解释在 C++ 中查找奇数和子数组的数量的所有可能信息。为了找到奇数和的子数组的数量，我们可以使用不同的方法，所以这里有一个简单的例子 −
输入:数组 = {9,8,7,6,5}
输出:9
解释:
子数组的总和 -
{9} = 9
{7} = 7
{5} = 5
{9,8} = 17
{8,7} = 15
{7,6} = 13
{6,5} = 11
{8,7,6} = 21
{9,8,7,6,5} = 35
强力方法
使用这种方法，我们可以简单地检查所有子数组中元素的总和是偶数还是奇数，如果是偶数，我们将拒绝该子数组并计算总和为奇数的子数组，这不是一种有效的方法方法，因为此代码的复杂度为 O(n2)。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int n=5, temp = 0;
int a[n-1] = { 9,8,7,6,5 } ; // 声明我们的数组。
int cnt = 0; // 计数器变量。
for(int i = 0; i < n; i++){
temp = 0; // 刷新我们的临时总和。
for(int j = i; j < n; j++){//此循环将使我们的子数组从 i 开始直到 n-1。
temp = temp + a[j];
if( temp % 2 == 1 )
cnt++;
}
}
cout << "奇数和的子数组数量:" << cnt << "\n";
return 0;
}
输出
奇数和的子数组数量:9
上述代码的解释
此代码中使用了嵌套循环，其中外循环用于增加 I 的值，该值从起始位置指向数组的每个值;内循环用于从位置 " i" 开始查找具有奇数和的子数组。
高效方法
在这种方法中，我们从数组中的第 0 个位置开始处理每个元素。如果当前元素为奇数，则增加奇数计数器，并为每个偶数增加偶数计数器。如果我们发现一个奇数，则交换偶数和奇数的值，因为向子数组添加奇数将改变其奇偶性，并最终向结果添加一个计数。此代码的复杂度为 O(n)，因为我们正在处理每个元素。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int odd = 0, even = 0, result = 0,n=5,i,temp;
int arr[ n-1 ] = { 9,8,7,6,5}; // initialising the array
// for 循环处理数组的每个元素
for ( i = 0 ; i < n ; i ++ ) {
if ( arr[ i ] % 2 == 0 ) {
even++;
} else {
// 交换偶数奇数值
temp = even;
even = odd;
odd = temp + 1;
}
result += odd;
}
cout << "总和为奇数的子数组数量:<< result;
}
输出
奇数和的子数组数量:9
上述代码的解释
在此代码中，我们检查每个元素的偶数/奇数，如果是偶数则增加偶数计数器，如果是奇数则增加奇数计数器。此外，如果发现奇数，我们将交换奇偶计数器值;否则，它将改变子数组的奇偶性。然后在每次迭代后将奇数计数器的值添加到结果变量中。
结论
在本文中，我们解释了如何从蛮力方法中找到奇数和的子数组的数量，即生成每个奇数和的子数组并增加计数。此代码的时间复杂度为 O(n2)。一种有效的方法是遍历数组的每个元素，并随着找到的每个奇数/偶数增加奇数/偶数计数器变量，如果找到奇数则交换计数器;此代码的时间复杂度为 O(n)。希望您发现本文有助于理解问题和解决方案。
