Метод двух указателей

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]