子數(shù)組是數(shù)組的連續(xù)部分。例如，我們考慮一個數(shù)組 [5, 6, 7, 8]，那么有十個非空子數(shù)組，如 (5), (6), (7), (8), (5, 6), (6 ,7)、(7,8)、(5,6,7)、(6,7,8) 和 (5,6,7,8)。
在本指南中，我們將解釋在 C++ 中查找所有可能的信息來查找具有奇數(shù)和的子數(shù)組的數(shù)量。為了找到奇數(shù)和的子數(shù)組的數(shù)量，我們可以使用不同的方法，所以這里是一個簡單的例子 –
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
登錄后復(fù)制
暴力方法
通過這種方法，我們可以簡單地檢查所有子數(shù)組中元素的總和是偶數(shù)還是奇數(shù)，如果是偶數(shù)，我們將拒絕該子數(shù)組并計算總和為奇數(shù)的子數(shù)組，這不是一種有效的方法，因為此代碼的復(fù)雜度為 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 } ; // declaring our array.
int cnt = 0; // counter variable.
for(int i = 0; i < n; i++){
temp = 0; // refreshing our temp sum.
for(int j = i; j < n; j++){ // this loop will make our subarrays starting from i till n-1.
temp = temp + a[j];
if( temp % 2 == 1 )
cnt++;
}
}
cout << "Number of subarrays with odd sum : " << cnt << "\n";
return 0;
}
登錄后復(fù)制
輸出
Number of subarrays with odd sum : 9
登錄后復(fù)制登錄后復(fù)制
上述代碼說明
此代碼中使用了嵌套循環(huán)，其中外層循環(huán)用于遞增 I 的值，I 指向數(shù)組從頭開始的每個值；內(nèi)循環(huán)用于查找從位置 ” i “ 開始的具有奇數(shù)和的子數(shù)組。
高效方法
在這種方法中，我們正在處理每個從數(shù)組中第 0 個位置開始的元素。如果當(dāng)前元素是奇數(shù)，則為每個偶數(shù)增加一個奇數(shù)計數(shù)器并增加一個偶數(shù)計數(shù)器。如果我們找到一個奇數(shù)，則交換 Even 和 odd 的值，因為向子數(shù)組添加奇數(shù)會改變其奇偶校驗，最后向結(jié)果添加一個計數(shù)。這段代碼的復(fù)雜度是 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 loop for processing every element of array
for ( i = 0 ; i < n ; i ++ ) {
if ( arr[ i ] % 2 == 0 ) {
even++;
} else {
// swapping even odd values
temp = even;
even = odd;
odd = temp + 1;
}
result += odd;
}
cout << "Number of subarrays with odd sum : " << result;
}
登錄后復(fù)制
輸出
Number of subarrays with odd sum : 9
登錄后復(fù)制登錄后復(fù)制
上述代碼的解釋
在這段代碼中，我們檢查每個元素的偶數(shù)/奇數(shù)，并為偶數(shù)增加偶數(shù)計數(shù)器，為奇數(shù)增加奇數(shù)計數(shù)器。此外，如果找到奇數(shù)，我們將交換奇偶計數(shù)器值；否則，它將改變子數(shù)組的奇偶校驗。然后在每次迭代后將奇數(shù)計數(shù)器的值添加到結(jié)果變量中。
結(jié)論
在本文中，我們解釋了如何從 Brute 中查找總和為奇數(shù)的子數(shù)組的數(shù)量強制方法，生成每個子數(shù)組的總和為奇數(shù)并遞增計數(shù)。這段代碼的時間復(fù)雜度是O(n2)。一種有效的方法是遍歷數(shù)組的每個元素，并用找到的每個奇數(shù)/偶數(shù)增加奇數(shù)/偶數(shù)計數(shù)器變量，如果找到奇數(shù)則交換計數(shù)器；這段代碼的時間復(fù)雜度是O(n)。希望您發(fā)現(xiàn)本文有助于理解問題和解決方案。
以上就是使用C++編寫代碼，找到具有奇數(shù)和的子數(shù)組的數(shù)量的詳細(xì)內(nèi)容，更多請關(guān)注www.xfxf.net其它相關(guān)文章！
