Урок 5: Массивы и два указателя

Представьте книжную полку, где книги стоят вплотную друг к другу: нужна третья? Отсчитайте три и сразу перейдите к ней. Это массив — доступ к элементу по индексу занимает O(1). Сегодня мы познакомимся с изящным приёмом — «два указателя»: вместо одного маркера, который просматривает всё подряд, вы за

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

два указателя: Паттерн, в котором два индекса перемещаются по массиву (от концов внутрь или в одном направлении), чтобы решить задачу за один проход.
на месте (in-place): Изменение данных внутри существующей структуры без выделения новой — O(1) дополнительной памяти.
непрерывная память: Хранение элементов рядом друг с другом в памяти, что обеспечивает доступ по индексу за O(1) и удобный для кэша обход.