Что такое техника двух указателей?

Question

Accepted Answer

Техника **двух указателей** использует два индекса, которые движутся по последовательности, чтобы решить задачи за один проход — превращая множество решений O(n²) на силовой перебор в **O(n)**.

## Идея

Сохраняйте два указателя (часто на концах, или один медленный и один быстрый) и перемещайте их на основе условия, сокращая работу без повторного сканирования.

## Пример: пара, которая суммируется до целевого значения в отсортированном массиве

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # found the pair
        elif s < target:
            lo += 1               # need a bigger sum
        else:
            hi -= 1               # need a smaller sum
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3) for 4 + 6
```

## Сложность

- **Время:** O(n). **Пространство:** O(1).

## Когда использовать / ловушки

Отлично подходит для **отсортированных массивов**, проверок палиндромов, разворота и удаления дубликатов на месте. Массив часто должен быть отсортирован для варианта сходящихся указателей. Будьте осторожны с границами указателя и условием цикла (`lo < hi`).

## Почему это важно

Два указателя — это один из наиболее эффективных паттернов собеседования: он преобразует вложенные циклы в чистое линейное сканирование.

Он учит вас использовать структуру (такую как отсортированность) вместо грубой силы.

Ста же идея лежит в основе слияния, партиционирования и шага слияния сортировки слиянием.