使用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 中尋找所有可能的資訊來尋找具有奇數和的子陣列的數量。為了找到奇數和的子數組的數量，我們可以使用不同的方法，所以這裡是一個簡單的例子-

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(n²)。

範例

#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;
}

輸出

Number of subarrays with odd sum : 9

上述程式碼說明

此程式碼中使用了巢狀循環，其中外層循環用於遞增I 的值，I 指向數組從頭開始的每個值；內循環用於查找從位置" i " 開始的具有奇數和的子數組。

高效方法

在這個方法中，我們正在處理每個從陣列中第 0 個位置開始的元素。如果目前元素是奇數，則為每個偶數增加一個奇數計數器並增加一個偶數計數器。如果我們找到一個奇數，則交換 Even 和 odd 的值，因為向子數組添加奇數會改變其奇偶校驗，最後向結果添加一個計數。這段程式碼的複雜度是 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;
}

輸出

Number of subarrays with odd sum : 9

上述程式碼的解釋

在這段程式碼中，我們檢查每個元素的偶數/奇數，並為偶數增加偶數計數器，為奇數增加奇數計數器。此外，如果找到奇數，我們將交換奇偶計數器值；否則，它將改變子數組的奇偶校驗。然後在每次迭代後將奇數計數器的值加到結果變數中。

結論

在本文中，我們解釋如何從 Brute 中找到總和為奇數的子數組的數量強制方法，產生每個子數組的總和為奇數並遞增計數。這段程式碼的時間複雜度是O(n2)。一個有效的方法是遍歷數組的每個元素，並用找到的每個奇數/偶數增加奇數/偶數計數器變量，如果找到奇數則交換計數器；這段代碼的時間複雜度是O(n)。希望您發現本文有助於理解問題和解決方案。

以上是使用C++編寫程式碼，找到具有奇數和的子數組的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！