Два указателя и скользящее окно

Перед началом: срезы и строки изнутри (модуль 2). Инструменты: Go 1.27, playground курса. Трудоёмкость: ~5 ч (теория 1.5 ч · практика 3.5 ч).

🔥 Инцидент: «Отчёт, который считался 40 минут»

Аналитикам нужен был показатель: самая длинная серия событий в логе, где event_id не повторяются (признак «чистой» сессии без ретраев). Инженер написал честный перебор: для каждой позиции начала — идти вперёд, пока значения уникальны, на каждом шаге проверяя по срезу уже собранных. Отчёт на тестовых 50 000 строк шёл две секунды, на продовых 2 миллионах — 40 минут: O(n²) плюс линейный поиск внутри дал кубический рост. Задача, однако, решается за один проход: правый указатель расширяет окно, левый подтягивается, как только внутри окна появляется дубликат.

📖 Теория

3.1 Инвариант вместо перебора

Два указателя работают, когда есть монотонность: если окно «плохое», то любое его расширение тоже плохое. Тогда не нужно проверять все окна — достаточно двигать границы только вперёд. Суммарно каждый указатель проходит массив один раз → O(n) вместо O(n²).

Два базовых движения:

• встречное — left с начала, right с конца, сходятся к середине (пары, палиндромы, слияние двух отсортированных);
• однонаправленное (fast/slow или окно) — оба идут слева направо, расстояние между ними задаёт смысл (окно, медленный/быстрый).

3.2 Встречные указатели

Классика: в отсортированном срезе найти пару с суммой target. Вложенный цикл даст O(n²); встречный указатель — O(n), потому что больше не нужно рассматривать пары «мимо»:

go
func twoSumSorted(a []int, target int) (int, int, bool) {
	left, right := 0, len(a)-1
	for left < right {
		sum := a[left] + a[right]
		switch {
		case sum == target:
			return left, right, true
		case sum < target:
			left++ // сумма мала только с этим left — сдвигаем вправо
		default:
			right-- // сумма велика: уменьшаем правый конец
		}
	}
	return -1, -1, false
}

Инвариант — «ответ, если существует, лежит в текущем [left, right]». Каждый шаг сокращает интервал и не теряет ни одной валидной пары: это и есть доказательство корректности, которое на собеседовании спрашивают чаще, чем код.

3.3 Медленный и быстрый

Тот же приём без окна — две скорости на одном массиве. Удаление дубликатов in-place из отсортированного среза:

go
func dedup(a []int) int {
	if len(a) == 0 {
		return 0
	}
	slow := 0 // последняя записанная уникальная позиция
	for fast := 1; fast < len(a); fast++ {
		if a[fast] != a[slow] {
			slow++
			a[slow] = a[fast]
		}
	}
	return slow + 1 // длина «сжатого» префикса
}

Бонус работы in-place: ноль аллокаций — редкий случай, когда O(n) по времени и O(1) по памяти одновременно.

3.4 Фиксированное окно

Когда ширина окна задана (k), сумма пересчитывается за O(1) на сдвиг: вычесть ушедший элемент, добавить пришедший. Максимальная сумма k подряд идущих:

go
func maxWindowSum(a []int, k int) int {
	if len(a) < k || k <= 0 {
		return 0
	}
	sum := 0
	for i := 0; i < k; i++ {
		sum += a[i]
	}
	best := sum
	for i := k; i < len(a); i++ {
		sum += a[i] - a[i-k]
		if sum > best {
			best = sum
		}
	}
	return best
}

Наивная версия — O(n·k), окно — O(n). При k = 1000 разница уже заметна на миллионе элементов.

3.5 Динамическое окно

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

go
left := 0
counts := make(map[byte]int)
best := 0
for right := 0; right < len(s); right++ {
	counts[s[right]]++        // расширяем окно
	for counts[s[right]] > 1 { // инвариант нарушен — сжимаем
		counts[s[left]]--
		left++
	}
	// здесь окно [left, right] всегда «хорошее» — обновляем ответ
	if right-left+1 > best {
		best = right - left + 1
	}
}

Это и есть решение инцидента из начала модуля: самая длинная подстрока без повторяющихся символов. Внутренний for не делает алгоритм квадратичным: left двигается только вперёд, суммарно — O(n).

Родственный шаблон — «минимальное окно, удовлетворяющее условию»: здесь внешний цикл растёт правым краем, а внутренний сжимает слева, пока условие выполняется, и ответ обновляется в момент сжатия.

3.6 Компромиссы

Монотонность — условие применимости. Окно не работает, если «плохо на префиксе» не значит «плохо на расширении»: например, максимальная сумма подотрезка с отрицательными числами — это задача префиксных сумм или DP (модуль 16), а не скользящего окна.

💻 Практика

1. Удаление дубликатов in-place. Дан отсортированный []int. Верните длину массива без дублей, не создавая второй срез (данные — первые len элементов). Сравните с решением через map из модуля 1: что быстрее и почему на отсортированных данных.
2. Пара с суммой (sorted). Реализуйте twoSumSorted из §3.2 и напишите табличный тест: пустой срез, пара в начале, пара в конце, пары нет, все элементы одинаковые. Объясните, почему алгоритм не пропустит пару (i, j) при сдвиге указателя.
3. Окно фиксированной ширины. maxWindowSum(a, k) из §3.4 и вторая функция — «среднее по окну» для каждой позиции за O(n) (ответ — срез средних). Замерьте на n = 1 000 000, k = 1000: ваша версия против наивной.
4. Самая длинная подстрока без повторов. Решите задачу из инцидента модуля. Требование: один проход, O(1) дополнительной памяти сверх массива счётчиков. Проверьте на "abcabcbb" → 3 (abc), "bbbbb" → 1, "" → 0, "pwwkew" → 3.
5. Минимальное окно с суммой ≥ S. Дан срез положительных чисел и S. Найдите минимальную длину подотрезка с суммой не меньше S (или 0, если нет). Проверьте: почему здесь работает окно, а при отрицательных числах — нет (приведите контрпример).

🧩 Quiz

✅ Итоги модуля

• Два указателя и окно — это инвариант + монотонность: каждый шаг сокращает пространство поиска, не теряя ответ.
• Встречные указатели — пары и палиндромы в отсортированных данных; fast/slow — in-place преобразования без аллокаций.
• Фиксированное окно обновляется за O(1) на сдвиг; динамическое — по шаблону «расширяем, пока хорошо; сжимаем, пока плохо».
• Применимость ограничена монотонностью: отрицательные числа и немонотонные условия ломают окно — там нужны префиксные суммы или DP.

🔗 Мостик к Модулю 4

В шаблоне окна мы уже использовали map для счётчика частот, приняв его O(1) на веру. В следующем модуле заглянем внутрь: как устроена хеш-таблица в Go, почему порядок итерации по map случаен, во что обходится плохая хеш-функция — и напишем свою таблицу с бакетами и цепочками, чтобы сравнить её с map бенчмарком.