Calcul de sous-tableaux à somme fixe

Pour identifier rapidement les sous-sequences contiguës dont la somme équivaut à une valeur cible, la technique des sommes préfixées couplée à une table de dispersion s'avère optimale. En définissant P[j] comme la somme des éléments jusqu'à l'indice j, la somme d'un sous-tableau allant de i à j-1 s'exprime par P[j] - P[i] = cible. Cette équation peut être réarrangée en P[i] = P[j] - cible.

Lors du parcours du tableau, il suffit de compter combien de fois la valeur P[j] - cible a déjà été rencontrée. Pour gérer correctement les sous-tableaux débutant à l'indice 0, on initialise la table de dispersion avec l'entrée {0: 1}, représentant la somme nulle avant le premier élément. Il est crucial d'interroger la table avant d'y enregistrer la somme courante ; cet ordre évite de compter incorrectement des sous-tableaux vides lorsque la cible est nulle.

class Solution {
public:
    int compterSousTableaux(const vector<int>& tableau, int cible) {
        int total = 0;
        int sommeCourante = 0;
        unordered_map<int, int> historique;
        historique.reserve(tableau.size());
        historique[0] = 1;

        for (int val : tableau) {
            sommeCourante += val;
            int requis = sommeCourante - cible;
            auto it = historique.find(requis);
            if (it != historique.end()) {
                total += it->second;
            }
            historique[sommeCourante]++;
        }
        return total;
    }
};

La complexité temporelle reste linéaire O(n) grâce à l'accès constant de la table de dispersion, tandis que l'espace mémoire requis est O(n) dans le pire des cas pour stocker les sommes préfixées distinctes.

Maximum dans une fenêtre coulissante

Le suivi du maximum dans une fenêtre de taille fixe peut être réalisé sans recalcul complet à chaque décalage, en exploitant une file double (deque) monotone. Cette structure conserve les indices des éléments dans un ordre strictement décroisant de leurs valeurs. Lorsqu'un nouvel élément arrive, on purge la queue de la file en retirant tous les indices dont les valeurs associées sont inférieures ou égales à l'élément courant, préservant ainsi la propriété monotone.

La tête de la file pointe toujours vers l'indice du maximum local. Avant d'enregistrer le résultat, on vérifie si cet indice est toujours contenu dans la fenêtre courante ; sinon, il est retiré. Stocker les indices plutôt que les valeurs brutes simplifie la détection des éléments expirés.

class Solution {
public:
    vector<int> extraireMaximums(const vector<int>& donnees, int tailleFenetre) {
        vector<int> resultats;
        deque<int> file;

        for (int i = 0; i < donnees.size(); ++i) {
            while (!file.empty() && donnees[file.back()] <= donnees[i]) {
                file.pop_back();
            }
            file.push_back(i);

            if (file.front() <= i - tailleFenetre) {
                file.pop_front();
            }

            if (i >= tailleFenetre - 1) {
                resultats.push_back(donnees[file.front()]);
            }
        }
        return resultats;
    }
};

Chaque élément est inséré et retiré au plus une fois de la deque, garantissant une complexité temporelle de O(n) et une occupation mémoire de O(k).

Sous-chaîne minimale couvrante

Pour trouver la plus courte sous-chaîne d'un texte contenant tous les caractères d'un modèle, la méthode de la fenêtre glissante est privilégiée. On maintient deux pointeurs délimitant la fenêtre courante et un compteur indiquant combien de caractères requis par le modèle sont actuellement satisfaits. En étendant la fenêtre vers la droite, on décrémente les compteurs des caractères rencontrés. Dès que tous les besoins du modèle sont comblés, on contracte la fenêtre par la gauche pour minimiser sa taille, tout en réincrémentant les compteurs et en ajustant le compteur de satisfaction.

class Solution {
public:
    string obtenirFenetreMinimale(string source, string modele) {
        if (modele.empty() || source.empty()) return "";
        
        array<int, 128> compteurs{};
        for (char c : modele) compteurs[c]++;
        
        int gauche = 0, droite = 0;
        int satisfait = 0;
        int meilleurDebut = -1, meilleureLongueur = INT_MAX;

        while (droite < source.size()) {
            char cDroite = source[droite++];
            compteurs[cDroite]--;
            if (compteurs[cDroite] >= 0) satisfait++;

            while (satisfait == modele.size()) {
                if (droite - gauche < meilleureLongueur) {
                    meilleurDebut = gauche;
                    meilleureLongueur = droite - gauche;
                }
                char cGauche = source[gauche++];
                compteurs[cGauche]++;
                if (compteurs[cGauche] > 0) satisfait--;
            }
        }
        return (meilleurDebut == -1) ? "" : source.substr(meilleurDebut, meilleureLongueur);
    }
};

Cette approche parcourt le texte une seule fois. Chaque caractère est visité au maximum deux fois (une fois par droite, une fois par gauche), aboutissant à une complexité temporelle de O(m) et une complexité spatiale de O(1) (alphabet constant).

Marquage en place d'une matrice à zéro

Lors de la mise à zéro des lignes et colonnes contenant initialement un zéro, un espace supplémentaire O(1) est atteignable en utilisant la première ligne et la première colonne de la matrice comme tableaux de signaux. Deux booléens indépendants sont néanmoins requis pour conserver l'état initial de la première ligne et de la première colonne, car celles-ci serviront de zones de stockage.

L'algorithme se déroule en quatre phases : vérification préalable de la première ligne et colonne, marquage des signaux dans le reste de la grille, application des signaux pour transformer les cellules internes, et enfin réinitialisation de la première ligne et colonne selon les booléens enregistrés.

class Solution {
public:
    void propagerZero(vector<vector<int>>& grille) {
        int lignes = grille.size();
        int colonnes = grille[0].size();
        bool colInitZero = false;
        bool ligneInitZero = false;

        for (int r = 0; r < lignes; ++r) {
            if (grille[r][0] == 0) { colInitZero = true; break; }
        }
        for (int c = 0; c < colonnes; ++c) {
            if (grille[0][c] == 0) { ligneInitZero = true; break; }
        }

        for (int r = 1; r < lignes; ++r) {
            for (int c = 1; c < colonnes; ++c) {
                if (grille[r][c] == 0) {
                    grille[r][0] = 0;
                    grille[0][c] = 0;
                }
            }
        }

        for (int r = 1; r < lignes; ++r) {
            for (int c = 1; c < colonnes; ++c) {
                if (grille[r][0] == 0 || grille[0][c] == 0) {
                    grille[r][c] = 0;
                }
            }
        }

        if (colInitZero) {
            for (int r = 0; r < lignes; ++r) grille[r][0] = 0;
        }
        if (ligneInitZero) {
            for (int c = 0; c < colonnes; ++c) grille[0][c] = 0;
        }
    }
};

Le traitement effectue deux passages complets sur les éléments de la matrice, conservant une complexité temporelle de O(m \times n) tout en éliminant la dépendance à des structures de données auxiliaires.