EN ES DE

Meisterung der Two-Pointers-Technik

4. März 2026
algorithmen arrays interview-vorbereitung typescript
In this article

Die Two-Pointers-Technik ist eines der verbreitetsten und effektivsten Muster zur Lösung von Array- und String-Problemen. Anstelle von verschachtelten Schleifen (O(n2)O(n^2)) verwenden wir zwei Variablen (Pointer), um die Datenstruktur zu durchlaufen, was oft eine Zeitkomplexität von O(n)O(n) ermöglicht.

1. Verifizierung eines Alien-Wörterbuchs

In einer außerirdischen Sprache verwenden sie unsere Buchstaben, aber in einer anderen Reihenfolge. Gegeben eine Liste von Wörtern und die Reihenfolge des Alien-Alphabets, müssen wir prüfen, ob die Wörter lexikografisch sortiert sind.

/**
 * Überprüft, ob Wörter basierend auf einer benutzerdefinierten Alphabet-Reihenfolge sortiert sind.
 * @param words - Array von Strings
 * @param order - Die Reihenfolge des Alien-Alphabets
 */
function isAlienSorted(words: string[], order: string): boolean {
  const orderMap = new Map<string, number>();
  for (let i = 0; i < order.length; i++) {
    orderMap.set(order[i], i);
  }


  for (let i = 0; i < words.length - 1; i++) {
    const word1 = words[i];
    const word2 = words[i + 1];


    if (!compareWords(word1, word2, orderMap)) {
      return false;
    }
  }


  return true;
}


function compareWords(w1: string, w2: string, map: Map<string, number>): boolean {
  const minLen = Math.min(w1.length, w2.length);


  for (let i = 0; i < minLen; i++) {
    if (w1[i] !== w2[i]) {
      return (map.get(w1[i]) || 0) < (map.get(w2[i]) || 0);
    }
  }


  // Wenn eines ein Präfix des anderen ist, muss das kürzere zuerst kommen
  return w1.length <= w2.length;
}

[!TIP] Lexikografischer Tipp: Behandeln Sie immer den “Präfix”-Fall. Wenn word1 “apple” und word2 “app” ist, sollte word1 in jedem gültigen Wörterbuch nach word2 kommen.

2. Zusammenführen sortierter Arrays (In-place)

Führen Sie zwei sortierte Arrays nums1 und nums2 in nums1 als ein sortiertes Array zusammen. nums1 hat genug Platz (Nullen am Ende), um nums2 aufzunehmen.

/**
 * Führt nums2 in-place in nums1 zusammen.
 */
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  let p1 = m - 1; // Letztes Element der tatsächlichen Daten in nums1
  let p2 = n - 1; // Letztes Element in nums2
  let p3 = m + n - 1; // Letzte Position in nums1


  while (p2 >= 0) {
    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
      nums1[p3] = nums1[p1];
      p1--;
    } else {
      nums1[p3] = nums2[p2];
      p2--;
    }
    p3--;
  }
}

[!SUCCESS] Trick: Beim In-place-Zusammenführen, wenn das Ziel am Ende zusätzlichen Platz hat, iterieren Sie rückwärts. Dies verhindert das Überschreiben von Elementen, die Sie noch nicht verarbeitet haben!

3. Behälter mit dem meisten Wasser

Finden Sie zwei Linien, die einen Behälter bilden, der die größte Menge an Wasser enthält.

export function maxArea(heights: number[]): number {
  let left = 0;
  let right = heights.length - 1;
  let maxAreaValue = 0;


  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(heights[left], heights[right]);
    const area = minHeight * width;


    maxAreaValue = Math.max(maxAreaValue, area);


    // Greedy-Move: Den Pointer bewegen, der auf die kürzere Linie zeigt
    if (heights[left] < heights[right]) {
      left++;
    } else {
      right--;
    }
  }


  return maxAreaValue;
}

[!IMPORTANT] Begründung: Beim Wasserbehälter-Problem bewegen wir die kürzere Seite, da das Bewegen der längeren Seite nur die Breite verringern kann, ohne die Chance zu haben, die Höhe zu erhöhen (die Höhe wird durch die kürzere Seite begrenzt).

4. Nullen verschieben

Verschieben Sie alle 0en an das Ende des Arrays, während die relative Reihenfolge der Nicht-Null-Elemente beibehalten wird.

function moveZeroes(nums: number[]): void {
  let lastNonZeroFoundAt = 0;


  // Wenn das aktuelle Element nicht 0 ist, müssen wir es
  // vor das letzte gefundene Nicht-Null-Element anhängen.
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      nums[lastNonZeroFoundAt++] = nums[i];
    }
  }


  // Nachdem wir die Verarbeitung der neuen Elemente abgeschlossen haben,
  // befinden sich alle Nicht-Null-Elemente bereits am Anfang des Arrays.
  // Wir müssen nur das restliche Array mit 0en füllen.
  for (let i = lastNonZeroFoundAt; i < nums.length; i++) {
    nums[i] = 0;
  }
}

Zusammenfassung der Muster

  1. Gegenüberliegende Seiten: Pointer starten bei 0 und length - 1 (z.B. Palindrom, Wasserbehälter).
  2. Gleiche Seite (Slow/Fast): Beide starten bei 0, bewegen sich aber mit unterschiedlicher Geschwindigkeit oder unter verschiedenen Bedingungen (z.B. Nullen verschieben, Duplikate entfernen).
  3. Rückwärts: Starten am Ende, um Platz in-place zu füllen (z.B. Zusammenführen sortierter Arrays).