Two Pointers und Sliding Window: Array- und String-Optimierungstechniken

1. Übersicht

Wenn du auf ein Problem triffst, bei dem du ein Array oder eine Zeichenkette durchsuchen musst und die Brute-Force-Lösung O(n²) oder O(n³) läuft, helfen dir die beiden Techniken Two Pointers und Sliding Window oft dabei, die Komplexität auf O(n) zu senken. Dieser Artikel erklärt die Kernidee jeder Technik anhand konkreter Java-Beispiele: Two Sum auf sortiertem Array, Palindrome-Überprüfung, maximale Summe in einem festen Fenster und längster Substring ohne wiederholte Zeichen. Danach wirst du das Muster erkennen und es auf viele ähnliche Probleme anwenden können.

2. Was ist Two Pointers?

Two Pointers ist eine Technik, bei der zwei Index-Variablen (Pointer) über eine Datenstruktur (meist ein sortiertes Array oder eine Zeichenkette) bewegt werden, um verschachtelte Schleifen zu vermeiden. Die beiden Pointer können sich bewegen:

• In die gleiche Richtung (fast/slow): wird für das Entfernen von Duplikaten und das Erkennen von Zyklen verwendet.
• In entgegengesetzte Richtungen (left/right von beiden Enden): wird zum Finden von Paaren mit einer bestimmten Summe und zur Überprüfung von Palindromen verwendet.

2.1. Two Pointers in entgegengesetzten Richtungen: Paar mit Zielsum finden

Klassisches Problem: Gegeben ein aufsteigendes sortiertes Array, finde zwei Zahlen, deren Summe dem Zielwert entspricht.

public class TwoSumSorted {

    public int[] findPair(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{numbers[left], numbers[right]};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[0];
    }
}

Erklärung:

• left startet am Anfang des Arrays, right am Ende.
• Wenn sum < target, ist die Zahl bei left zu klein, also erhöhen wir left, um eine größere Zahl zu erhalten.
• Wenn sum > target, ist die Zahl bei right zu groß, also verringern wir right.
• Die Schleife läuft maximal n Schritte, da left oder right jedes Mal um ein Feld verschoben werden, was eine Komplexität von O(n) statt O(n²) bei verschachtelten Schleifen ergibt.

Test mit JUnit 5 + AssertJ:

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.10.2</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.25.3</version>
    <scope>test</scope>
</dependency>

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class TwoSumSortedTest {

    private final TwoSumSorted twoSum = new TwoSumSorted();

    @Test
    void shouldFindPairWhenSumMatchesTarget() {
        int[] numbers = {1, 3, 5, 8, 11};

        int[] result = twoSum.findPair(numbers, 13);

        assertThat(result).containsExactly(5, 8);
    }
}

Hinweis: Diese Technik erfordert ein sortiertes Array. Wenn das Array noch nicht sortiert ist, musst du es zuerst sortieren (O(n log n)) oder ein HashMap verwenden, um O(n) ohne Sortieren zu erreichen.

2.2. Two Pointers zur Palindrome-Überprüfung

public class PalindromeChecker {

    public boolean isPalindrome(String text) {
        int left = 0;
        int right = text.length() - 1;

        while (left < right) {
            if (text.charAt(left) != text.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Die beiden Pointer starten von beiden Enden der Zeichenkette, vergleichen Zeichen und bewegen sich zur Mitte. Wenn ein Zeichenpaar unterschiedlich ist, wird sofort false zurückgegeben – kein vollständiger Durchlauf erforderlich. Das ist der Grund, warum diese Technik schneller ist als das Umkehren und Vergleichen der Zeichenkette (reverse().equals()), da das Erstellen eines zwischenzeitlichen StringBuilder-Objekts vermieden wird.

3. Was ist Sliding Window?

Sliding Window ist eine Variante von Two Pointers, die auf Probleme mit zusammenhängenden Teilfolgen (Subarrays/Substrings) angewendet wird. Statt die Berechnung für jede Startposition von vorne zu beginnen, behältst du ein „Fenster” [left, right] bei und aktualisierst es schrittweise, während das Fenster gleitet, und wiederverwendest frühere Ergebnisse.

Es gibt zwei Arten:

• Fixed-size Window: Die Fenstergröße ist fest (z. B. k Elemente).
• Variable-size Window: Die Größe variiert je nach Bedingung des Problems.

3.1. Fixed-size Window: maximale Summe eines Subarrays der Größe k

public class MaxSumSubarray {

    public int maxSum(int[] numbers, int windowSize) {
        int windowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            windowSum += numbers[i];
        }

        int maxSum = windowSum;
        for (int right = windowSize; right < numbers.length; right++) {
            windowSum += numbers[right] - numbers[right - windowSize];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
}

Erklärung:

• Die erste Schleife berechnet die Summe des ersten Fensters (vom Index 0 bis windowSize - 1).
• Danach wird das Fenster bei jedem Schritt um eins nach rechts verschoben: das neue Element hinzufügen (numbers[right]), das Element, das aus dem Fenster austritt, subtrahieren (numbers[right - windowSize]).
• Dadurch kostet jeder Schritt nur O(1) statt die Summe neu zu berechnen O(k), die Gesamtkomplexität beträgt O(n).

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class MaxSumSubarrayTest {

    private final MaxSumSubarray solver = new MaxSumSubarray();

    @Test
    void shouldReturnMaxSumOfWindowSizeThree() {
        int[] numbers = {2, 1, 5, 1, 3, 2};

        int result = solver.maxSum(numbers, 3);

        assertThat(result).isEqualTo(9); // Fenster [5, 1, 3]
    }
}

3.2. Variable-size Window: längster Substring ohne wiederholte Zeichen

In diesem Problem passt sich das Fenster der Bedingung „keine wiederholten Zeichen” an.

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    public int lengthOfLongestSubstring(String text) {
        Map<Character, Integer> lastSeenIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < text.length(); right++) {
            char current = text.charAt(right);
            if (lastSeenIndex.containsKey(current) && lastSeenIndex.get(current) >= left) {
                left = lastSeenIndex.get(current) + 1;
            }
            lastSeenIndex.put(current, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

Erklärung:

• right schreitet immer voran (erweitert das Fenster), left springt nur, wenn ein wiederholtes Zeichen innerhalb des aktuellen Fensters auftritt.
• lastSeenIndex speichert die zuletzt gesehene Position jedes Zeichens, um zu wissen, wohin left springen muss.
• Die Bedingung lastSeenIndex.get(current) >= left stellt sicher, dass das Zeichen nur als „dupliziert” gilt, wenn es noch im aktuellen Fenster liegt, und verhindert, dass left falsch nach hinten springt.
• Jedes Zeichen wird genau einmal bei right verarbeitet, daher beträgt die Gesamtkomplexität O(n).

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class LongestUniqueSubstringTest {

    private final LongestUniqueSubstring solver = new LongestUniqueSubstring();

    @Test
    void shouldReturnLengthOfLongestUniqueSubstring() {
        int result = solver.lengthOfLongestSubstring("abcabcbb");

        assertThat(result).isEqualTo(3); // "abc"
    }

    @Test
    void shouldHandleAllSameCharacters() {
        int result = solver.lengthOfLongestSubstring("bbbbb");

        assertThat(result).isEqualTo(1);
    }
}

Ausgabe beim manuellen Debuggen mit "abcabcbb":

right=0 'a' -> Fenster="a"    Länge=1
right=1 'b' -> Fenster="ab"   Länge=2
right=2 'c' -> Fenster="abc"  Länge=3
right=3 'a' -> Duplikat, left=1 -> Fenster="bca" Länge=3
right=4 'b' -> Duplikat, left=2 -> Fenster="cab" Länge=3
...
maxLength = 3

4. Vergleich und wann welche Technik zu verwenden ist

Situation	Geeignete Technik
Sortiertes Array, finde Paar/Triplet, die Summenbedingung erfüllen	Two Pointers in entgegengesetzten Richtungen
Überprüfe Symmetrie (Palindrome), kehre Array in-place um	Two Pointers in entgegengesetzten Richtungen
Entferne Duplikate in sortiertem Array	Two Pointers in die gleiche Richtung (fast/slow)
Subarray/Substring mit fester Größe k	Sliding Window fixed-size
Subarray/Substring erfüllen dynamische Bedingung (keine Wiederholungen, Summe ≤ Zielwert, …)	Sliding Window variable-size

Gemeinsamkeit: Beide Techniken vermeiden Neuberechnungen bereits verarbeiteter Teile und verringern die Komplexität von O(n²) auf O(n), indem sie den Zustand (Summe, Set, Map) aufrechterhalten, während sich der Pointer/das Fenster bewegt.

5. Häufige Fehler

• Die Stoppbedingung left < right vergessen: Dies kann zu einer Endlosschleife oder zum Vergleichen eines Elements mit sich selbst führen, wenn left == right.
• Two Pointers auf ein unsortiertes Array anwenden, ohne vorher zu sortieren – das Ergebnis ist völlig falsch, da die Pointer-Erhöhungs-/Verringerungslogik auf der Monotonie des Arrays basiert.
• Im Sliding Window die Statusaktualisierung vergessen, wenn left verschoben wird: z. B. das alte Element nicht aus HashMap/sum entfernen, was dazu führt, dass das Fenster Daten „merkt”, die nicht mehr zum Fenster gehören.
• Die Bedingungen zum Erweitern/Verkleinern des Fensters verwechseln: Bei einem Variable-size Window musst du klar definieren, welche Bedingung right vorantreibt und welche left – wenn du sie umkehrst, wird sich das Fenster nicht richtig verengen.

Hinweis: Diese beiden Techniken sind nicht geeignet, wenn das Problem alle zusammenhangslosen Subsets erfordert (z. B. Subset Sum) – dafür benötigst du Backtracking oder dynamische Programmierung, nicht Sliding Window.

6. Fazit

Two Pointers und Sliding Window sind zwei grundlegende Werkzeuge zur Lösung von Array-/String-Problemen mit linearer Komplexität. Das Erkennen des Musters – ein sortiertes Array, das ein Paar findet, oder zusammenhängende Subarrays/Substrings, die optimiert werden müssen – hilft dir, die richtige Technik zu wählen und kurzen, leicht zu testenden Code wie in den obigen Beispielen zu schreiben. Beim Üben solltest du versuchen, den Zustand von left/right bei jedem Schritt selbst zu skizzieren, um die Invariante zu verstehen, bevor du den Code schreibst.