使用C++編寫一個程式來找到具有給定範圍內和的子數組的數量

在本文中，我們將使用 C 程式來求解總和在給定範圍內的子陣列的數量。我們有一個正整數數組 arr[] 和一個範圍 {L, R}，我們必須計算總和在給定範圍 L 到 R 內的子數組的總數。所以這是該問題的簡單範例-

Input : arr[] = {1, 4, 6}, L = 3, R = 8

Output : 3

The subarrays are {1, 4}, {4}, {6}.


Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13

Output : 6

The subarrays are {2, 3}, {2, 3, 5}, {3, 5},
{5}, {5, 8}, {8}.

尋找解決方案的方法

我們將解釋使用C 問題解決此問題的兩種方法-

暴力方法

最基本的暴力方法方法用於計算每個子陣列的總和，然後找出該總和是否存在於給定範圍內。 （但這種方法會花費我們很多時間，因為它的時間複雜度是 O(n*n)，其中 n 是陣列的大小）。

高效的方法

節省現在，有效的方法是使用滑動視窗技術，使用這種技術，我們將在 O(n) 內更快或更有效地計算結果。

範例

#include <bits/stdc++.h>
using namespace std;
int subCount(int *arr, int n, int x){
    int start = 0, end = 0, sum = 0, count = 0;
    while (end < n){ // we will be moving right border in this loop
        sum = sum + arr[end];
        while(start <= end && sum >= x){ // this loop will move our left border
            sum = sum - arr[start]; // we will decrement sum while moving left border.
                                   // For excluding the previous elements.
            start++;                // and move the left border.
        }
        count = count + ((end - start) + 1); // counting the subarrays.
        end++;
    }
    return count;
}
int main(){
    int arr[] = { 1, 4, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int L = 3;
    int R = 8;
    int answer;
    answer = subCount(arr, n, R)  - subCount(arr, n, (L - 1)); // Final Answer.
    cout << answer << "\n";
    return 0;
}

輸出

3

上述程式碼說明

在這種方法中，我們計算總和小於給定範圍上限的子陣列的數量，然後減去總和小於給定範圍上限的子數組的數量。使用 subcount 函數小於給定範圍的下限。

Subcount 函數

該函數使用滑動視窗技術來尋找計數小於x 的子數組的計數.

首先，我們從「結束」和「開始」開始，其值均為0。當我們遍歷數組時，我們會維護從頭到尾的元素總和。之後，如果我們的開始等於結束並且總和大於或等於 x，我們開始移動開始並在從總和中取出元素時不斷減少總和。

直到我們的總和變得小於 x 或我們的開始變得大於結束。現在，我們將計數增加子數組計數，然後將右邊界增加 1。現在，在外循環結束後，我們傳回子數組的總計數。

結論

在本文中，我們使用滑動視窗技術解決了一個問題，即在 O(n) 時間複雜度內找到總和在給定範圍內的子數組的數量。我們還從C 程式中學習了這個問題以及我們可以輕鬆解決這個問題的完整方法（正常且有效率）。我們可以用其他語言（例如 C、java、python 等）來寫相同的程式。

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