1. Calcul du Nombre de Sous-tableaux Ayant une Somme Cible

L'objectif est de déterminer le nombre de sous-tableaux contigus dont la somme des éléments est exactement égale à une valeur cible. L'approche naïve en O(N²) est inefficace pour de grands ensembles de données. La solution optimale repose sur l'utilisation des sommes préfixées combinées à une table de hachage.

Le concept clé est de stocker les occurrences de chaque somme préfixée rencontrée. Pour une somme préfixée courante S, nous cherchons combien de fois la valeur S - cible est apparue précédemment. Une initialisation cruciale de la table de hachage avec la clé 0 (valeur 1) est nécessaire pour capturer correctement les sous-tableaux qui commencent directement à l'indice zéro du tableau.

int compterSousTableauxCible(const std::vector<int>& elements, int sommeCible) {
    std::unordered_map<int, int> occurrencesSommes;
    occurrencesSommes[0] = 1; // Initialisation critique pour les sous-tableaux démarrant à l'indice 0
    int totalCorrespondances = 0;
    int sommeActuelle = 0;

    for (int val : elements) {
        sommeActuelle += val;
        int complement = sommeActuelle - sommeCible;
        
        // Si le complément a été vu auparavant, on ajoute ses occurrences au résultat
        if (occurrencesSommes.find(complement) != occurrencesSommes.end()) {
            totalCorrespondances += occurrencesSommes[complement];
        }
        
        // Enregistrer la somme préfixée courante
        occurrencesSommes[sommeActuelle]++;
    }
    return totalCorrespondances;
}

2. Extraction du Maximum dans une Fenêtre Glissante

Pour trouver le maximum dans chaque fenêtre de taille fixe K glissant sur un tableau, une file d'attente classique est inadaptée car elle ne permet pas de retrouver le maximum en O(1). Nous devons concevoir une file doublement liée monotone (monotonic deque).

Cette structure maintient les éléments de manière strictement décroissante. Le maximum de la fenêtre courante se trouve toujours à l'avant de la file. Lors de l'ajout d'un nouvel élément, tous les éléments plus petits situés à l'arrière sont supprimés, car ils ne pourront jamais être le maximum tant que le nouvel élément est dans la fenêtre. Lors du déplacement de la fenêtre vers la droite, si l'élément en tête de file sort de la fenêtre, il est retiré.

class FileMonotone {
private:
    std::deque<int> elementsFenetre;
public:
    // Retirer l'élément s'il sort de la fenêtre et qu'il est le maximum actuel
    void retirerSiObsolet(int valeurSortante) {
        if (!elementsFenetre.empty() && elementsFenetre.front() == valeurSortante) {
            elementsFenetre.pop_front();
        }
    }

    // Maintenir la propriété monotone décroissante
    void inserer(int nouvelleValeur) {
        while (!elementsFenetre.empty() && elementsFenetre.back() < nouvelleValeur) {
            elementsFenetre.pop_back();
        }
        elementsFenetre.push_back(nouvelleValeur);
    }

    int obtenirMaximum() const {
        return elementsFenetre.front();
    }
};

std::vector<int> extraireMaximumsFenetre(const std::vector<int>& donnees, int tailleFenetre) {
    FileMonotone file;
    std::vector<int> resultats;

    // Initialisation de la première fenêtre
    for (int i = 0; i < tailleFenetre; ++i) {
        file.inserer(donnees[i]);
    }
    resultats.push_back(file.obtenirMaximum());

    // Glissement de la fenêtre
    for (size_t i = tailleFenetre; i < donnees.size(); ++i) {
        file.retirerSiObsolet(donnees[i - tailleFenetre]); // Contraction à gauche
        file.inserer(donnees[i]);                         // Extension à droite
        resultats.push_back(file.obtenirMaximum());
    }
    return resultats;
}

3. Recherche de la Plus Petite Sous-chaîne Couvrante

Ce problème demande de trouver la plus petite sous-chaîne de source qui contient tous les caractères de cible, y compris leurs fréquences. L'algorithme de la fenêtre glissante est idéal ici.

Puisque les caractères sont limités à l'ensemble ASCII, l'utilisation de tableaux de fréquences de taille fixe est beaucoup plus rapide qu'une table de hachage. Pour optimiser la vérification de la condition de couverture, au lieu de parcourir les tableaux à chaque itération, nous utilisons un compteur caracteresFormes qui s'incrémente lorsque la fréquence d'un caractère dans la fenêtre atteint exactement sa fréquence requise dans la cible. La fenêtre se contracte à gauche tant que la condition de couverture est satisfaite, permettant ainsi de mettre à jour la longueur minimale de manière optimale.

std::string trouverFenetreMinimale(const std::string& source, const std::string& cible) {
    std::vector<int> freqCible(128, 0);
    for (char c : cible) {
        freqCible[c]++;
    }

    // Compter le nombre de caractères uniques requis
    int caracteresUniquesRequis = 0;
    for (int count : freqCible) {
        if (count > 0) caracteresUniquesRequis++;
    }

    std::vector<int> freqFenetre(128, 0);
    int caracteresFormes = 0;
    int debutMeilleureFenetre = -1;
    int longueurMinimale = INT_MAX;
    int debutFenetre = 0;

    for (int finFenetre = 0; finFenetre < source.length(); ++finFenetre) {
        char cDroite = source[finFenetre];
        freqFenetre[cDroite]++;

        // Si la fréquence du caractère correspond exactement à l'exigence
        if (freqCible[cDroite] > 0 && freqFenetre[cDroite] == freqCible[cDroite]) {
            caracteresFormes++;
        }

        // Tant que la fenêtre est valide, on essaie de la réduire
        while (caracteresFormes == caracteresUniquesRequis) {
            if (finFenetre - debutFenetre + 1 < longueurMinimale) {
                longueurMinimale = finFenetre - debutFenetre + 1;
                debutMeilleureFenetre = debutFenetre;
            }

            char cGauche = source[debutFenetre];
            freqFenetre[cGauche]--;
            // Si on retire un caractère critique, la fenêtre n'est plus valide
            if (freqCible[cGauche] > 0 && freqFenetre[cGauche] < freqCible[cGauche]) {
                caracteresFormes--;
            }
            debutFenetre++;
        }
    }

    return debutMeilleureFenetre == -1 ? "" : source.substr(debutMeilleureFenetre, longueurMinimale);
}