Zwei Zeiger in einem sortierten Array
Bewegen Sie die Enden nach innen, bis Sie ein Ziel erreichen
Zwei Zeiger in einem sortierten Array ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 1 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.
Warum zwei Zeiger
Die Two-Pointer-Technik durchläuft ein Array mit zwei Indizes statt mit verschachtelten Schleifen und verwandelt viele Ansätze mit O(n^2) in einen einzigen übersichtlichen Durchlauf mit O(n). 🎯
Sortiert ist das Zauberwort
Die klassische Variante benötigt ein sortiertes Array. Durch die Ordnung können Sie logisch vorgehen: Eine Bewegung nach rechts erhöht den Wert, eine nach links verringert ihn, sodass jeder Schritt eine echte Entscheidung ist.
Zwei Zeiger an den Enden
Starten Sie einen Zeiger am left-Ende und einen am right-Ende. Die beiden zeigen aufeinander zu und schließen die Lücke zwischen ihnen langsam.
left = 0
right = len(a) - 1Die Enden nach innen verschieben
Bei jedem Schritt verschieben Sie genau einen Zeiger nach innen. Die Ordnung des Arrays zeigt Ihnen, welche Seite Sie anpassen müssen, um Ihrem Ziel näher zu kommen.
Die Schleifenbedingung
Wiederholen Sie die Schleife, solange left < right gilt. Sobald die Zeiger sich treffen oder kreuzen, wurde jedes nützliche Paar geprüft und Sie können anhalten.
while left < right:
# inspect a[left] and a[right]
passDie aktuelle Summe ablesen
Betrachten Sie a[left] + a[right] als Ihre aktuelle Kandidatensumme. Der Vergleich mit einem Zielwert zeigt Ihnen, ob Sie als Nächstes einen größeren oder kleineren Wert benötigen.
total = a[left] + a[right]Zu klein: left verschieben
Wenn die Summe unter dem Zielwert liegt, benötigen Sie mehr. Verschieben Sie den left-Zeiger nach rechts in Richtung größerer Werte, da das Array aufsteigend sortiert ist.
if total < target:
left += 1Zu groß: right verschieben
Wenn die Summe über dem Zielwert liegt, benötigen Sie weniger. Verschieben Sie den right-Zeiger nach links in Richtung kleinerer Werte, um die Gesamtsumme zu verringern.
elif total > target:
right -= 1Jeder Schritt verwirft Arbeit
Jede Bewegung beseitigt eine ganze Gruppe von Paaren, die Sie nicht mehr prüfen müssen. Deshalb ist der Durchlauf linear statt quadratisch.
Warum die Methode korrekt bleibt
Sie verwerfen nur Paare, die nicht passen können, sodass die richtige Antwort niemals übersprungen wird. Diese Sicherheit macht zwei Zeiger bei Wettbewerben zuverlässig.
Über die Endpunkte hinaus
Dieselbe Idee bildet die Grundlage für Varianten: Umkehren an Ort und Stelle, Partitionieren und Zusammenführen. Wenn Sie die sich treffenden Zeiger beherrschen, wirken all diese Aufgaben vertraut.
Kurzer Check
Sie durchlaufen ein sortiertes Array von beiden Enden aus, um eine Zielsumme zu finden.
Zusammenfassung
Zwei Zeiger durchlaufen ein sortiertes Array von beiden Enden aus und verschieben bei jedem Schritt einen Zeiger nach innen, solange left < right gilt. Linear, korrekt und die Grundlage vieler Tricks. 🚀
Häufig gestellte Fragen
Ist die Lektion „Zwei Zeiger in einem sortierten Array“ kostenlos?
Ja — der vollständige Text von „Zwei Zeiger in einem sortierten Array“ 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 „Zwei Zeiger in einem sortierten Array“?
Bewegen Sie die Enden nach innen, bis Sie ein Ziel erreichen 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 1 von 4.
Wie lange dauert die Lektion „Zwei Zeiger in einem sortierten Array“?
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