Ermitteln Sie in C++ die Anzahl der Subarrays, deren Summe kleiner als K ist

In diesem Beitrag ermitteln wir die Anzahl der Subarrays mit einer Summe kleiner als K unter Verwendung von C++. In diesem Problem haben wir ein Array arr[] und eine Ganzzahl K. Jetzt müssen wir die Subarrays finden, deren Summe kleiner als K ist. Unten ist das Beispiel –

Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3}

Weg, die Lösung zu finden

Jetzt werden wir zwei verschiedene Methoden verwenden, um das gegebene Problem zu lösen –

Brute Force

Bei dieser Methode werden wir alle Unterarrays durchlaufen und ihre Summe berechnen und Wenn die Summe kleiner als k ist, vergleichen Sie mit k, um unsere Antwort zu erhöhen.

Beispiel

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = {1, 11, 2, 3, 15}; // given array
    int k = 10; // given k
    int size = sizeof(arr) / sizeof(int); // size of our array.
    int ans = 0; // counter variable.
    for(int i = 0; i < size; i++){ // outer loop.
        int sum = 0;
        for(int j = i; j < size; j++){ // inner loop.
            sum = sum + arr[j];
            if(sum < k) // comparing with k.
               ans++; // incrementing our ans if sum is less than k.
        }
    }
    cout << ans << "\n";
    return 0;
}

Ausgabe

4

Diese Methode ist jedoch nicht sehr gut, da ihre zeitliche Komplexität sehr hoch ist O(N*N), wobei n die Größe des Arrays ist.

Wir suchen nach alternativen Lösungen mithilfe des Sliding-Window-Ansatzes (dies wird uns helfen, die zeitliche Komplexität des Programms zu reduzieren).

Effiziente Methode

Im Gegensatz zur Brute Force

effizienten Methode

strong> iterieren wir nicht durch alle Unterarrays. Stattdessen iterieren wir nur dann, wenn die Summe der Unterarrays k überschreitet, verschieben die linke Grenze zur rechten Grenze und wiederholen dies, bis das gesamte Array durchlaufen ist.

Beispiel

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = {1, 11, 2, 3, 15}; // given array
    int k = 10; // given k
    int size = sizeof(arr) / sizeof(int); // size of our array.
    int ans = 0; // counter variable.
    int start = 0; // left border.
    int end = 0; // right border.
    int sum = 0;
    while(end < size && start < size){ // till the whole array is traversed.
        while(sum >= k && start < end){
           sum = sum - arr[start];
           start++;
        }
        if(end >= start)
           ans = ans + end - start;
        sum += arr[end];
        end++;
    }
    cout << ans << "\n";
    return 0;
}

Ausgabe

4

Wir verwenden die Sliding-Window-Technik, um unser Programm bei größeren Einschränkungen schneller oder effizienter zu machen.

Erklärung des obigen Codes

Bei diesem Ansatz iterieren wir normalerweise, bis unsere Summe kleiner als k ist, und erhöhen unsere Antwort darauf basierend. Dies ist die entscheidende Änderung im Code, die auftritt, wenn die Summe größer oder gleich k ist . In diesem Fall beginnen wir mit der Erhöhung unserer linken Grenze, bis sie kleiner oder gleich k ist oder die Summe größer oder gleich k ist. Während unsere Verarbeitung weiter voranschreitet, iteriert sie durch andere mögliche Unterarrays, die möglicherweise gebildet werden. Die Summe dieser neuen Unterarrays, die kleiner als k sind, wird zu unserer Antwort addiert, sodass unsere Antwort inkrementiert wird.

Im Vergleich zur vorherigen Brute-Force-Lösung ist diese Methode sehr effizient, da ihre Zeitkomplexität O(N) beträgt, wobei N die Größe unseres Arrays ist.

Fazit

In diesem Artikel haben wir das Problem gelöst, die Anzahl der Subarrays zu ermitteln, deren Summe kleiner als k ist, indem wir die Schiebefenstertechnik verwenden. Wir haben auch ein C++-Programm für dieses Problem und unseren vollständigen Lösungsansatz (sowohl trivial als auch effizient) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Ich hoffe, Sie finden diesen Artikel hilfreich.

Das obige ist der detaillierte Inhalt vonErmitteln Sie in C++ die Anzahl der Subarrays, deren Summe kleiner als K ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!