Два указателя

Two pointers заменяют nested scans, когда правила движения исключают невозможных candidates. Pointers могут сходиться с концов, двигаться с разной скоростью или поддерживать write position при чтении. Pattern лучше всего работает с sorted arrays, linked list cycles, partitioning и in-place compaction.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Интервьюеры слушают invariant, который делает безопасным сдвиг одного pointer вместо перебора каждой пары.

Типовые ошибки: Не используйте pattern, если порядок input не поддерживает elimination. Осторожно обрабатывайте duplicates, equality cases и момент движения pointer до или после обработки.

Чеклист:

• Назовите elimination rule.
• Обработайте equality.
• Двигайте pointers монотонно.
• Проверьте inputs с большим числом duplicates.