Zwei-Zeiger-Methode

2.1 Definition der Zwei-Zeiger-Methode.

Die Zwei-Zeiger-Methode ist eine Technik, die zur Lösung verschiedener Aufgaben mit Arrays und Strings eingesetzt wird. Dabei werden zwei Zeiger (Indizes) verwendet, die sich nach bestimmten Regeln durch die Daten bewegen. Diese Methode ermöglicht es, effizient Aufgaben zu lösen, die mit der Suche nach Paarelementen und Teilmengen verbunden sind, die bestimmten Bedingungen genügen.

Diese Methode setzt voraus, dass zwei Zeiger verwendet werden, die normalerweise an den gegenüberliegenden Enden der Datenstruktur initialisiert werden und sich aufeinander zu oder nach einer bestimmten Regel bewegen. Die Zwei-Zeiger-Methode kann die Zeitkomplexität eines Algorithmus im Vergleich zu naiveren Ansätzen erheblich reduzieren.

Grundprinzipien

1. Initialisierung der zwei Zeiger: Die Zeiger können am Anfang und Ende eines Arrays oder Strings oder an verschiedenen Indizes je nach Aufgabe platziert werden.
2. Bewegung der Zeiger: Die Zeiger bewegen sich nach einer bestimmten Regel (zum Beispiel beide Zeiger bewegen sich auf das Zentrum zu, oder ein Zeiger bewegt sich vorwärts, während der andere an Ort und Stelle bleibt).
3. Bedienungsprüfung: Bei jedem Schritt wird eine Bedingung überprüft, die die weitere Bewegung der Zeiger oder den Abschluss des Algorithmus bestimmt.

Zeitkomplexität:

O(n) — in den meisten Fällen, da beide Zeiger ein oder mehrere Male das Array durchlaufen, aber nicht mehr als O(n) Iterationen insgesamt.

Für einige Aufgaben kann die Zeitkomplexität je nach Bedingungen und Startpositionen der Zeiger O(n log n) oder O(n^2) sein, aber das ist selten.

Beispiele für Aufgaben, die mit der Zwei-Zeiger-Methode gelöst werden können:

2.2 Suche nach zwei Zahlen in einem Array, deren Summe einer gegebenen Zahl entspricht.

Aufgabe:

Finde zwei Zahlen in einem sortierten Array, deren Summe eine gegebene Zahl target ergibt.

Lösung:

Initialisiere einen Zeiger am Anfang des Arrays, den anderen am Ende. Überprüfe die Summe der Elemente unter den Zeigern:

• Wenn die Summe gleich target ist, gib die Indizes zurück.
• Wenn die Summe kleiner als target ist, bewege den linken Zeiger nach rechts.
• Wenn die Summe größer als target ist, bewege den rechten Zeiger nach links.

Zeitkomplexität: O(n).

Beispielcode in Python:

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
        

2.3 Palindromprüfung

Aufgabe:

Überprüfen, ob ein String ein Palindrom ist.

Lösung:

Initialisiere Zeiger am Anfang und Ende des Strings. Vergleiche die Zeichen unter den Zeigern:

• Wenn die Zeichen gleich sind, bewege beide Zeiger aufeinander zu.
• Wenn die Zeichen nicht gleich sind, ist der String kein Palindrom.

Zeitkomplexität: O(n).

Beispielcode in Python:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
        

2.4 Entfernen von Duplikaten aus einem sortierten Array

Aufgabe:

Entferne Duplikate aus einem sortierten Array.

Lösung:

Nutze zwei Zeiger, einen für die aktuelle Position im Ergebnisarray, den anderen zur Iteration über alle Elemente:

• Wenn das aktuelle Element ungleich dem vorhergehenden ist, schreibe es in das Ergebnisarray.

Zeitkomplexität: O(n).

Beispielcode in Python:

def remove_duplicates(arr):
    if not arr:
        return 0
    write_index = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_index] = arr[i]
            write_index += 1
    return write_index