Ein Paar mit einer gegebenen Summe finden
Übertreffen Sie die Brute-Force-Methode mit O(n^2)
Ein Paar mit einer gegebenen Summe finden ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 2 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 Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Das Two-Sum-Problem
Gegeben sind ein Array und ein Zielwert. Finden Sie zwei Werte, die zusammen diesen Wert ergeben. Das ist eine der häufigsten Einstiegsaufgaben bei Wettbewerben. 🔍
Der Brute-Force-Ansatz
Der naheliegende Ansatz prüft mit zwei verschachtelten Schleifen jedes Paar. Er funktioniert, aber die Prüfung aller Paare kostet O(n^2) und kann viel zu langsam sein.
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return (i, j)Wo Brute Force scheitert
Bei einem n nahe 100000 bedeutet O(n^2) zehn Milliarden Prüfungen, und Sie erhalten einen TLE. Die Grenzen zeigen Ihnen, dass Sie etwas Schnelleres finden müssen.
Sortieren, dann durchlaufen
Wenn Sie das Array zuerst sort, lösen zwei Zeiger von beiden Enden die Aufgabe in einem Durchlauf. Das Sortieren kostet O(n log n), der anschließende Durchlauf O(n).
a.sort()
left, right = 0, len(a) - 1Mit dem Zielwert vergleichen
Lesen Sie bei jedem Schritt a[left] + a[right] ab. Diese eine Zahl bestimmt Ihren nächsten Schritt, ohne dass Sie raten müssen.
total = a[left] + a[right]Exakte Übereinstimmung: fertig
Wenn die Summe dem Zielwert entspricht, haben Sie das Paar gefunden. Geben Sie es sofort zurück, da Sie nur eine gültige Antwort benötigen.
if total == target:
return (left, right)Andernfalls anpassen
Ist die Summe zu klein, verschieben Sie left nach rechts; ist sie zu groß, verschieben Sie right nach links. Die sortierte Reihenfolge garantiert, dass jede Bewegung hilft.
elif total < target:
left += 1
else:
right -= 1Kein Paar vorhanden
Wenn sich die Zeiger ohne Treffer kreuzen, gibt es kein gültiges Paar. Das Ende der Schleife ist selbst eine vollständige Antwort.
Die Hash-Set-Alternative
Wenn Sie die ursprünglichen Indizes beibehalten müssen, ist ein Hash-Set übersichtlicher: Prüfen Sie für jeden Wert, ob target minus dieser Wert bereits gesehen wurde.
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)Die passende Methode auswählen
Verwenden Sie zwei Zeiger, wenn das Array sortiert ist oder sortiert werden kann; verwenden Sie das Hash-Set, wenn Sie echtes O(n) ohne Sortieren benötigen oder die Indizes beibehalten müssen.
Auf Duplikate achten
Wenn ein Wert mit sich selbst ein Paar bilden kann, müssen Ihre beiden Indizes verschieden sein. Eine schnelle Prüfung mit left != right oder i != j verhindert diesen Fehler.
Kurzer Check
Sie möchten den Brute-Force-Ansatz mit O(n^2) bei der Suche nach einem Paar mit einer bestimmten Summe übertreffen.
Zusammenfassung
Sortieren Sie und durchlaufen Sie das Array dann mit zwei Zeigern, um ein Zielpaar in O(n log n) zu finden, oder verwenden Sie ein Hash-Set für O(n), wenn die Indizes wichtig sind. Entscheiden Sie anhand der Grenzen. ✅
Häufig gestellte Fragen
Ist die Lektion „Ein Paar mit einer gegebenen Summe finden“ kostenlos?
Ja — der vollständige Text von „Ein Paar mit einer gegebenen Summe finden“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Ein Paar mit einer gegebenen Summe finden“?
Übertreffen Sie die Brute-Force-Methode mit O(n^2) Du übst Competitive Programming Academy 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 Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy 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 2 von 4.
Wie lange dauert die Lektion „Ein Paar mit einer gegebenen Summe finden“?
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 Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-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
- Zwei Zeiger in einem sortierten Array
- Ein Paar mit einer gegebenen Summe finden
- Duplikate direkt entfernen
- Zwei sortierte Sequenzen zusammenführen