Compter les sous-tableaux d’une somme cible
Combiner les sommes préfixes avec une table de hachage
Compter les sous-tableaux d’une somme cible est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Une question plus difficile
Voici maintenant la difficulté : compter combien de sous-tableaux ont une somme égale à une valeur cible k. Vérifier chaque paire est lent, mais les sommes préfixes associées à une table de hachage permettent de résoudre le problème. 🎯
Reformulez avec les préfixes
La somme d'un sous-tableau est égale à prefix[r + 1] moins prefix[l]. Une somme égale à k signifie donc que deux valeurs de préfixe diffèrent exactement de k.
La réorganisation essentielle
Si le préfixe courant vaut P, vous avez besoin d'un préfixe antérieur égal à P moins k. Cette réorganisation est toute l'astuce.
need = current_prefix - kComptez au lieu de chercher
Au lieu de reparcourir les éléments précédents à chaque fois, mémorisez combien de fois chaque valeur de préfixe est apparue. Un compteur mis à jour au fil du parcours répond en O(1).
Utilisez une table de fréquences
Un dictionnaire associe chaque valeur de préfixe au nombre de fois où vous l'avez rencontrée. Cette table transforme la recherche en comptage instantané.
from collections import defaultdict
seen = defaultdict(int)Initialisez le préfixe vide
Avant la boucle, enregistrez que le préfixe 0 est apparu une fois. Cette initialisation permet de compter les sous-tableaux qui commencent à l'indice 0.
seen[0] = 1La boucle en un seul parcours
Pour chaque élément, mettez à jour le préfixe courant, ajoutez le nombre d'occurrences de la valeur recherchée, puis enregistrez le préfixe courant. Un seul parcours suffit.
total += x
count += seen[total - k]
seen[total] += 1Pourquoi l'ordre est important
Vous devez ajouter au résultat avant d'enregistrer le préfixe courant. Sinon, un intervalle de longueur nulle est compté et le comptage devient incorrect.
Le gain de vitesse
Chaque élément demande un travail constant, donc le comptage complet s'exécute en O(n). Cela surpasse la force brute en O(n carré) pour les grandes entrées.
Les nombres négatifs sont acceptés
Contrairement aux fenêtres glissantes, cette méthode gère parfaitement les nombres négatifs, car les différences de préfixes restent valides quels que soient les signes.
Un cas d'utilisation classique
Ce schéma résout le célèbre problème de la somme d'un sous-tableau égale à k ainsi que de nombreuses variantes déguisées dans les problèmes de concours.
Vérification rapide
Votre préfixe courant vaut P et la cible vaut k.
Récapitulatif
Vous pouvez compter les sous-tableaux dont la somme atteint la cible en O(n) grâce aux sommes préfixes et à une table de fréquences. Initialisez le préfixe 0, puis comptez avant d'enregistrer. ✅
Questions Fréquemment Posées
La leçon « Compter les sous-tableaux d’une somme cible » est-elle gratuite ?
Oui — le texte complet de « Compter les sous-tableaux d’une somme cible » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Compter les sous-tableaux d’une somme cible » ?
Combiner les sommes préfixes avec une table de hachage Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Compter les sous-tableaux d’une somme cible » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Construire un tableau de sommes préfixes
- Additionner n’importe quelle plage par soustraction
- Compter les sous-tableaux d’une somme cible
- Tableaux de différences pour les mises à jour de plages