Zwei Zeiger ist Monotonizität in Verkleidung.

Die meisten Erklärungen zu Two Pointers bringen dir das Muster bei. Linker Zeiger hier, rechter Zeiger dort, bewege einen, wenn eine bestimmte Bedingung erfüllt ist. Lerne die Vorlage auswendig und wende sie an.

Das funktioniert, bis sich die Aufgabe leicht ändert und du nicht mehr sagen kannst, ob Two Pointers überhaupt anwendbar ist. Dann rätst du nur noch.

Hier ist die zugrunde liegende Idee, die die meisten Erklärungen auslassen: Two Pointers funktioniert, wenn die relevante Eigenschaft des Fensters bezüglich der Zeigerbewegung monoton ist. Den rechten Zeiger vorwärts zu bewegen kann die Eigenschaft nur vergrößern. Den linken Zeiger vorwärts zu bewegen kann sie nur verkleinern. Das ist genau die Bedingung, die auch die binäre Suche korrekt macht. Sobald du das siehst, hört „Two Pointers oder binäre Suche?“ auf, ein Münzwurf zu sein.

Was Monotonie hier eigentlich bedeutet

Nimm den Klassiker: Finde zwei Indizes i < j in einem sortierten Array, sodass a[i] + a[j] = target.

Setze einen Zeiger an das linke Ende und einen an das rechte. Die Summe ist a[l] + a[r]. Bewegst du r nach links, sinkt die Summe. Bewegst du l nach rechts, steigt die Summe. Die Summe ist bezüglich beider Zeigerbewegungen monoton. Deshalb kannst du bei jedem Schritt Fortschritt machen: Ist die Summe zu groß, bewege r nach links; ist sie zu klein, bewege l nach rechts.

int l = 0, r = n - 1;
while (l < r) {
    int s = a[l] + a[r];
    if (s == target) { /* found */ break; }
    else if (s < target) l++;
    else r--;
}

Der Code ist fünf Zeilen lang. Der Grund, warum er funktioniert, ist ein einziger Satz: Die Summe ist monoton in l und monoton in r.

Sliding Window ist dieselbe Idee

Längster Teilstring mit höchstens K verschiedenen Zeichen. Das ist Two Pointers auf einem String, oft Sliding Window genannt. Die Eigenschaft hier ist: die Anzahl der verschiedenen Zeichen in [l, r]. Wenn r steigt, kann die Anzahl nur gleich bleiben oder wachsen. Wenn l steigt, kann sie nur gleich bleiben oder sinken. Monoton in beide Richtungen.

int l = 0, best = 0;
map<char, int> cnt;
for (int r = 0; r < n; r++) {
    cnt[s[r]]++;
    while ((int)cnt.size() > k) {
        cnt[s[l]]--;
        if (cnt[s[l]] == 0) cnt.erase(s[l]);
        l++;
    }
    best = max(best, r - l + 1);
}

Gleiche Struktur. Die while-Schleife bewegt l vorwärts, bis die Eigenschaft wiederhergestellt ist. Das ist gültig, weil das Erhöhen von l die Anzahl der verschiedenen Zeichen nur verringern kann — sie kann dadurch nicht schlechter werden.

Kleinstes Teilarray mit Summe mindestens S

Die Eigenschaft ist: die Summe des Fensters [l, r]. Monoton in r (das Bewegen nach rechts fügt ein positives Element hinzu, vorausgesetzt alle Elemente sind positiv), monoton in l (das Bewegen nach links entfernt ein Element). Der Algorithmus: erweitere r, bis die Summe S erreicht, verkleinere dann l so weit wie möglich, solange die Summe über S bleibt, und notiere dabei die Fensterlänge.

Beachte die Annahme: alle Elemente positiv. Daher kommt die Monotonie. Können Elemente negativ sein, kann das Verkleinern von l die Summe verringern, und die Eigenschaft ist nicht mehr monoton. Two Pointers würde falsche Antworten liefern, ohne jede Fehlermeldung. Ich komme später darauf zurück.

Wenn es unbemerkt kaputtgeht

Das ist der Teil, der Schülern zum Verhängnis wird. Two Pointers stürzt nicht ab, wenn die Monotonie-Annahme verletzt wird. Es liefert einfach falsche Antworten, und wenn deine Testfälle schwach sind, merkst du es nicht.

Angenommen, du hast ein Array mit negativen Elementen und willst das kürzeste Teilarray mit Summe mindestens S. Das Verkleinern von l könnte die Summe unter S drücken. Aber deine while-Schleife weiß das nicht — sie prüft nur die Bedingung und stoppt. Das Ergebnis sieht plausibel aus und ist falsch.

Die Frage, die du dir stellen solltest, bevor du eine Two-Pointer-Lösung schreibst: Was ist die Eigenschaft meines Fensters, und ist sie wirklich monoton, wenn ich jeden Zeiger bewege? Schreib das explizit auf. Wenn du die monotone Eigenschaft nicht benennen kannst, kannst du nicht überprüfen, ob der Algorithmus korrekt ist.

Wenn du die monotone Eigenschaft benennen kannst, schreibt sich die Zeigerbewegung von selbst.

Two Pointers gegen binäre Suche

Beide erfordern Monotonie. Der Unterschied liegt in den Kosten. Binäre Suche auf einer Funktion f(x) erfordert, dass du f(x) für einen einzelnen Punkt in O(log n) Runden auswertest — wenn die Auswertung von f billig ist (O(1) oder O(log n)), ist binäre Suche in Ordnung. Two Pointers amortisiert die Arbeit anders: jeder Zeiger bewegt sich insgesamt höchstens n Schritte, sodass die Gesamtkomplexität O(n) ist, unabhängig davon, was du pro Schritt tust, solange es O(1) ist.

Wenn deine Eigenschaft monoton ist und du sie inkrementell pflegen kannst, während das Fenster wächst oder schrumpft, liefert dir Two Pointers O(n). Wenn das inkrementelle Pflegen teuer ist, aber die Neuberechnung von Grund auf an einem festen Punkt schnell geht, ist binäre Suche sauberer. Oft funktionieren beide; Two Pointers hat tendenziell eine kleinere Konstante.

Das Two-Pointer-Muster ist kein Trick zum Auswendiglernen. Es ist eine Konsequenz aus einer einzigen Eigenschaft. Finde die Eigenschaft, prüfe, ob sie monoton ist, und der Rest des Codes ergibt sich direkt daraus.

Löse als Nächstes diese

Drei Aufgaben, die ich direkt im Anschluss an diesen Artikel empfehle. Jede zwingt dich dazu, die monotone Eigenschaft zu benennen, bevor der Code funktioniert:

• Codeforces 676C — Vasya and String. Hier sind sowohl Two Pointers als auch binäre Suche über die Antwort korrekt. Entscheide, welche der beiden du schreibst, und begründe warum — diese Entscheidung ist dieser ganze Artikel im Kleinen.
• CSES 1660 — Subarray Sums I. Alle Elemente positiv. Sauberes Sliding Window; benenne die Eigenschaft, dann schreib es.
• CSES 1661 — Subarray Sums II. Gleiche Aufgabenstellung, aber negative Zahlen sind erlaubt — und die Monotonie ist weg. Erkenne genau, wo deine Two-Pointer-Argumentation zusammenbricht, und löse es dann auf eine andere Weise.