Écrit en C++, trouvez le nombre de sous-tableaux dont la somme est inférieure à K

Dans cet article, nous trouverons le nombre de sous-tableaux dont la somme est inférieure à K en utilisant C++. Dans ce problème, nous avons un tableau arr[] et un entier K. Nous devons maintenant trouver les sous-tableaux dont la somme est inférieure à K. Vous trouverez ci-dessous l'exemple −

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

Façon de trouver la solution

Nous allons maintenant utiliser deux méthodes différentes pour résoudre le problème donné -

Force brute

Dans cette méthode, nous allons parcourir tous les sous-tableaux et calculer leur somme et si la somme est inférieure à k, comparez avec k pour augmenter notre réponse.

Exemple

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

Sortie

4

Cependant, cette méthode n'est pas très bonne car sa complexité temporelle est très élevée O(N*N), où n est la taille du tableau.

Nous rechercherons des solutions alternatives en utilisant une approche de fenêtre glissante (cela nous aidera à réduire la complexité temporelle du programme).

Méthode efficace

Contrairement à la force brute

méthode efficace

strong>, nous ne parcourons pas tous les sous-tableaux. Au lieu de cela, seulement lorsque la somme des sous-tableaux dépasse k , nous itérons et déplaçons la limite gauche vers la limite droite et répétons jusqu'à ce que tout le tableau soit parcouru.

Exemple

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

Sortie

4

Nous utilisons la Technique de fenêtre coulissante pour rendre notre programme plus rapide ou plus efficace face à des contraintes plus importantes.

Explication du code ci-dessus

Dans cette approche, nous itérons généralement jusqu'à ce que notre somme soit inférieure à k et incrémentons notre réponse en fonction de celle-ci, c'est le changement clé dans le code qui se produit lorsque la somme est supérieure ou égale à k . Dans ce cas, nous commençons à incrémenter notre limite gauche jusqu'à ce qu'elle soit inférieure ou égale à k ou que la somme soit supérieure ou égale à k. Au fur et à mesure que notre traitement progresse, il parcourt d'autres sous-réseaux possibles qui peuvent être formés. La somme de ces nouveaux sous-tableaux inférieure à k est ajoutée à notre réponse, donc notre réponse est incrémentée.

Par rapport à la solution de force brute précédente, cette méthode est très efficace car sa complexité temporelle est O(N), où N est la taille de notre tableau.

Conclusion

Dans cet article, nous avons résolu le problème de trouver le nombre de sous-tableaux dont la somme est inférieure à k en utilisant la technique de la fenêtre coulissante. Nous avons également appris un programme C++ pour ce problème et notre approche complète pour le résoudre (à la fois triviale et efficace). Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et autres. J'espère que cet article vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!