Метод двох вказівників

2.1 Визначення методу двох вказівників.

Метод двох вказівників — це техніка, що використовується для розв'язання різноманітних задач на масивах і рядках, при якій використовуються два вказівники (індекси), що переміщуються по даних за визначеними правилами. Цей метод дозволяє ефективно вирішувати задачі, пов'язані з пошуком пар елементів, підмножин, які задовольняють заданим умовам.

Цей метод передбачає використання двох вказівників, які зазвичай ініціалізуються на протилежних кінцях структури даних і переміщуються назустріч один одному або за певним правилом. Метод двох вказівників може значно зменшити часову складність алгоритму порівняно з більш наївними підходами.

Основні принципи

1. Ініціалізація двох вказівників: Вказівники можуть бути встановлені на початок і кінець масиву або рядка, або на різні індекси в залежності від задачі.
2. Переміщення вказівників: Вказівники переміщуються за визначеним правилом (наприклад, обидва вказівники рухаються до центру, або один вказівник рухається вперед, поки інший залишається на місці).
3. Перевірка умови: На кожному кроці перевіряється умова, яка визначає подальше переміщення вказівників або завершення алгоритму.

Часова складність:

O(n) — у більшості випадків, оскільки обидва вказівники проходять по масиву один або кілька разів, але не більше O(n) ітерацій у сумі.

Для деяких задач, в залежності від умов та початкових позицій вказівників, часова складність може бути O(n log n) або O(n^2), але це рідкість.

Приклади задач, що розв'язуються методом двох вказівників:

2.2 Пошук двох чисел у масиві, сума яких дорівнює заданому числу.

Задача:

Знайти два числа в відсортованому масиві, які в сумі дають задане число target.

Рішення:

Ініціалізуємо один вказівник на початок масиву, інший на кінець. Перевіряємо суму елементів під вказівниками:

• Якщо сума дорівнює target, повертаємо індекси.
• Якщо сума менша за target, зсуваємо лівий вказівник вправо.
• Якщо сума більша за target, зсуваємо правий вказівник вліво.

Часова складність: O(n).

Приклад коду на 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 Перевірка паліндрому

Задача:

Перевірити, чи є рядок паліндромом.

Рішення:

Ініціалізуємо вказівники на початок і кінець рядка. Порівнюємо символи під вказівниками:

• Якщо символи однакові, зсуваємо обидва вказівники назустріч один одному.
• Якщо символи не однакові, рядок не є паліндромом.

Часова складність: O(n).

Приклад коду на 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 Видалення дублікатів з відсортованого масиву

Задача:

Видалити дублікати з відсортованого масиву.

Рішення:

Використовуємо два вказівники, один для поточної позиції в результуючому масиві, інший для перебору всіх елементів:

• Якщо поточний елемент не дорівнює попередньому, записуємо його у результуючий масив.

Часова складність: O(n).

Приклад коду на Python:

def remove_duplicates(arr):
    if not arr:  # Якщо масив порожній, повертаємо порожній масив
        return []

    write_index = 1  # Вказівник для запису унікальних значень

    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:  # Якщо поточний елемент не дорівнює попередньому
            arr[write_index] = arr[i]  # Записуємо унікальний елемент на позицію write_index
            write_index += 1  # Зсуваємо вказівник

    return arr[:write_index]  # Повертаємо масив з унікальними значеннями, обрізаючи його до write_index

# Приклад використання
arr = [1, 1, 2, 2, 2, 3, 4, 4, 5]
result = remove_duplicates(arr)
print(result)  # Очікуваний результат: [1, 2, 3, 4, 5]