Metoda dwóch wskaźników

2.1 Definicja metody dwóch wskaźników.

Metoda dwóch wskaźników — to technika wykorzystywana do rozwiązania różnych zadań na tablicach i stringach, przy której używane są dwa wskaźniki (indeksy), które przemieszczają się po danych zgodnie z określonymi zasadami. Ta metoda pozwala efektywnie rozwiązywać zadania związane z poszukiwaniem par elementów, podzbiorów, które spełniają dane warunki.

Ta metoda zakłada użycie dwóch wskaźników, które zwykle są inicjalizowane na przeciwnych końcach struktury danych i przemieszczają się w stronę siebie lub zgodnie z określoną zasadą. Metoda dwóch wskaźników może znacznie zmniejszyć złożoność czasową algorytmu w porównaniu z bardziej naiwnymi podejściami.

Główne zasady

1. Inicjalizacja dwóch wskaźników: Wskaźniki mogą być ustawione na początek i koniec tablicy lub stringu, albo na różne indeksy w zależności od zadania.
2. Przemieszczanie wskaźników: Wskaźniki przemieszczają się zgodnie z określoną zasadą (na przykład, oba wskaźniki przesuwają się do środka, albo jeden wskaźnik przesuwa się do przodu, podczas gdy drugi pozostaje na miejscu).
3. Sprawdzenie warunku: Na każdym kroku sprawdzany jest warunek, który określa dalsze przemieszczanie wskaźników albo zakończenie algorytmu.

Złożoność czasowa:

O(n) — w większości przypadków, ponieważ oba wskaźniki przemieszczają się po tablicy jeden lub kilka razy, ale nie więcej niż O(n) iteracji w sumie.

Dla niektórych zadań, w zależności od warunków i początkowych pozycji wskaźników, złożoność czasowa może być O(n log n) albo O(n^2), ale to rzadkość.

Przykłady zadań rozwiązywanych metodą dwóch wskaźników:

2.2 Znajdowanie dwóch liczb w tablicy, których suma jest równa danemu numerowi.

Zadanie:

Znajdź dwie liczby w posortowanej tablicy, które sumują się do danego numeru target.

Rozwiązanie:

Inicjalizujemy jeden wskaźnik na początku tablicy, drugi na końcu. Sprawdzamy sumę elementów pod wskaźnikami:

• Jeśli suma jest równa target, zwracamy indeksy.
• Jeśli suma jest mniejsza od target, przesuwamy lewy wskaźnik w prawo.
• Jeśli suma jest większa od target, przesuwamy prawy wskaźnik w lewo.

Złożoność czasowa: O(n).

Przykład kodu w Pythonie:

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 Sprawdzenie czy palindrom

Zadanie:

Sprawdź, czy string jest palindromem.

Rozwiązanie:

Inicjalizujemy wskaźniki na początku i końcu stringu. Porównujemy znaki pod wskaźnikami:

• Jeśli znaki są równe, przesuwamy oba wskaźniki w stronę siebie.
• Jeśli znaki nie są równe, string nie jest palindromem.

Złożoność czasowa: O(n).

Przykład kodu w Pythonie:

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 Usuwanie duplikatów z posortowanej tablicy

Zadanie:

Usuń duplikaty z posortowanej tablicy.

Rozwiązanie:

Używamy dwóch wskaźników, jeden dla bieżącej pozycji w wynikowej tablicy, drugi do iteracji po wszystkich elementach:

• Jeśli bieżący element nie jest równy poprzedniemu, zapisujemy go w wynikowej tablicy.

Złożoność czasowa: O(n).

Przykład kodu w Pythonie:

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