使用 C++ 求奇数子数组的个数

2026-06-02 4 花语

子数组是数组的连续部分。例如，我们考虑一个数组[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++中找到具有奇数和的子数组的数量。为了找到具有奇数和的子数组的数量，我们可以使用不同的方法，所以这里有一个简单的例子-

Input : array = {9,8,7,6,5} Output : 9 Explanation : Sum of subarray - {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}; //初始化数组 //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).希望您发现这篇文章有助于理解问题和解决方案。