Schreiben Sie ein Programm mit C++, um die Anzahl der Subarrays mit der Summe in einem bestimmten Bereich zu ermitteln

In diesem Artikel verwenden wir ein C++-Programm, um die Anzahl der Unterarrays zu ermitteln, deren Summe innerhalb eines bestimmten Bereichs liegt. Wir haben ein Array positiver Ganzzahlen arr[] und einen Bereich {L, R} und müssen die Gesamtzahl der Unterarrays zählen, deren Summe in den angegebenen Bereich L bis R fällt. Hier ist also ein einfaches Beispiel des Problems –

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}.

Möglichkeiten, die Lösung zu finden

Wir erklären zwei Möglichkeiten, dieses Problem mit C++ zu lösen –

Brute-Force-Methode

Zur Berechnung wird jeweils die grundlegendste Brute-Force-Methode verwendet sub Die Summe eines Arrays und ermittelt dann, ob die Summe innerhalb des angegebenen Bereichs liegt. (Dieser Ansatz wird jedoch viel Zeit in Anspruch nehmen, da seine Zeitkomplexität O(n*n) beträgt, wobei n die Größe des Arrays ist.)

Effiziente Methode

Speichern Die effiziente Methode ist nun die Verwendung der Schiebefenstertechnik. Mit dieser Technik berechnen wir das Ergebnis schneller oder effizienter in O(n).

Beispiel

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

Ausgabe

3

Oben Codebeschreibung

Bei dieser Methode zählen wir die Anzahl der Unterarrays, deren Summe kleiner als die Obergrenze des angegebenen Bereichs ist, und subtrahieren dann die Anzahl der Unterarrays, deren Summe ist kleiner als die Obergrenze des angegebenen Bereichs. Verwenden Sie die Subcount-Funktion, um weniger als die Untergrenze eines bestimmten Bereichs zu erhalten.

Subcount-Funktion

Diese Funktion verwendet die Schiebefenstertechnik, um die Anzahl eines Subarrays zu ermitteln, dessen Anzahl kleiner als x ist.

Zunächst beginnen wir mit „Ende“ und „Start“, die beide den Wert 0 haben . Wenn wir über ein Array iterieren, behalten wir die Summe der Elemente vom Anfang bis zum Ende bei. Wenn danach unser Start gleich Ende ist und die Summe größer oder gleich x ist, beginnen wir mit der Verschiebung des Starts und verringern die Summe weiter, während wir Elemente aus der Summe herausnehmen.

Bis unsere Summe kleiner als x wird oder unser Anfang größer als unser Ende wird. Jetzt erhöhen wir die Anzahl um die Anzahl der Subarrays und erhöhen dann die rechte Grenze um 1. Nachdem die äußere Schleife beendet ist, geben wir nun die Gesamtzahl des Subarrays zurück.

Fazit

In diesem Artikel haben wir das Problem gelöst, die Anzahl der Subarrays zu ermitteln, deren Summe innerhalb eines bestimmten Bereichs in O(n)-Zeitkomplexität liegt, indem wir die Schiebefenstertechnik verwendet haben. Wir haben dieses Problem auch anhand eines C++-Programms kennengelernt und erfahren, wie wir es einfach (normal und effizient) lösen können. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python usw. schreiben.

Das obige ist der detaillierte Inhalt vonSchreiben Sie ein Programm mit C++, um die Anzahl der Subarrays mit der Summe in einem bestimmten Bereich zu ermitteln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!