Meet in the Middle
Halbieren Sie den Exponenten, indem Sie die Suche aufteilen
Meet in the Middle ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Wenn Brute Force zu langsam ist
Manche Probleme haben ein N von ungefähr 40, sodass das Ausprobieren aller 2^N Teilmengen aussichtslos ist. Meet-in-the-Middle rettet solche mittelgroßen Fälle. 🤝
Die Grundidee
Teilen Sie die Eingabe in zwei Hälften. Lösen Sie jede Hälfte per Brute Force und kombinieren Sie anschließend die beiden Teilergebnisse geschickt.
Den Exponenten halbieren
Zwei Hälften der Größe N/2 kosten jeweils 2^(N/2) statt insgesamt 2^N. Diese Quadratwurzel-Verkleinerung macht aus 2^40 ein handliches 2^20.
Ein klassisches Ziel: Subset Sum
Gesucht ist, ob eine Teilmenge die Zielsumme T ergibt. Subset Sum mit N nahe 40 ist das klassische Meet-in-the-Middle-Problem.
Die erste Hälfte aufzählen
Listen Sie jede Teilmengensumme der linken Hälfte auf und speichern Sie sie. Bei N/2 Elementen sind das nur 2^(N/2) Summen.
from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []Die zweite Hälfte aufzählen
Machen Sie dasselbe für die rechte Hälfte und erstellen Sie ihre vollständige Liste von Teilmengensummen. Nun haben Sie zwei handhabbare Listen.
Mit einer Abfrage kombinieren
Für jede rechte Summe r benötigen Sie eine linke Summe, die T minus r entspricht. Ein Set oder eine sortierte Liste macht diese Prüfung schnell.
need = T - r
found = need in left_setZwei Möglichkeiten zum Abgleichen
Für exakte Ziele verwenden Sie ein Hash-Set. Zum Zählen oder für möglichst nahe Summen sortieren Sie eine Hälfte und führen dort eine binäre Suche durch.
Der Zeitaufwand
Der Gesamtaufwand beträgt ungefähr 2^(N/2) mal einen logarithmischen Faktor für die Suche oder das Sortieren. Diese Komplexität macht N nahe 40 machbar.
Speicher ist der Kompromiss
Sie speichern eine vollständige Hälfte, daher wächst der Speicherbedarf auf 2^(N/2). Bewahren Sie nur das auf, was Sie innerhalb des Limits benötigen.
Wo es sonst noch glänzt
Neben Subset Sum können Sie es für die maximale Teilmenge unter einem Limit, das Zählen von Paaren und Probleme im Stil des diskreten Logarithmus verwenden. Es liebt eine klare Aufteilung.
Kurzer Check
Sie wenden Meet-in-the-Middle auf ein Teilmengenproblem mit N Elementen an. Wie hoch ist ungefähr der Zeitaufwand?
Zusammenfassung
Teilen Sie in zwei Hälften, lösen Sie beide per Brute Force und gleichen Sie anschließend die linken und rechten Summen ab. Sie haben ein wenig Speicher gegen eine enorme Beschleunigung eingetauscht. 🚀
Häufig gestellte Fragen
Ist die Lektion „Meet in the Middle“ kostenlos?
Ja — der vollständige Text von „Meet in the Middle“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Meet in the Middle“?
Halbieren Sie den Exponenten, indem Sie die Suche aufteilen Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Meet in the Middle“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Gewinn- und Verlustzustände in Spielen
- Nim und die Grundy-Zahl
- Meet in the Middle
- Schnell debuggen: Stresstests und Triage