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

Короткий ответ. Два указателя сходятся с концов отсортированного массива и ищут пару. Скользящее окно двигает оба индекса вперёд и отвечает про отрезок между ними. Чтобы их не путать, после каждой ошибки записывай паттерн, за которым потянулся. Через двадцать задач виден короткий список пар, которые путаешь именно ты.

В машинном обучении это называют матрицей ошибок. Строки это правда, столбцы это предсказание. Интересное всегда вне диагонали.

Почему «неверно» это мало

Сайт с задачами даёт один бит. Решено или нет.

Промахнуться можно четырьмя способами.

Не тот паттерн. Тот паттерн с забытым шагом. Верный подход со сломанным краем. Обычная опечатка.

Лечатся они по-разному.

Свёрнутые в один красный крестик, они не дают выбрать. И человек открывает следующую задачу.

Месяцы идут, место остаётся прежним.

Четыре пары, которые ловят почти всех

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

Префиксные суммы и окно. Окну нужна сумма, которая растёт при расширении.

Одно отрицательное число это убивает. Приходят префиксные суммы.

Сигнал это фраза «могут быть отрицательные числа». Её легко проскочить глазами. Поэтому условие читают дважды.

Перебор с возвратом и динамика. Оба перебирают варианты.

Возврату нужны все расстановки. Его цена это количество ответов.

Динамике нужно одно число. Она выбрасывает всё кроме лучшего.

Различение «перечислить или посчитать» решает большинство случаев.

Обход в ширину и Дейкстра. Одно и то же, пока у рёбер нет весов.

Без весов обход в ширину уже даёт кратчайший путь. С весами он молча возвращает неправильный ответ.

Молча неправильно хуже падения. Поэтому и существует Дейкстра.

Что записывать

Хватит трёх колонок.

• Что было на самом деле.
• За чем ты потянулся.
• Слово в условии, которое должно было тебя остановить.

Третья колонка это и есть лечение. Путаница почти всегда это невзвешенный сигнал.

То же утверждение есть в статье про распознавание паттернов.

К четвёртой записи одно и то же слово всплывёт снова.

Что делать с парой

Не перечитывай оба паттерна. Напиши своими словами одно предложение, которое их разделяет.

«Окно корректно, у двух указателей массив отсортирован». «Возврат перечисляет, динамика считает».

Потом возьми две задачи, по одной на каждый, и сделай подряд. Для первой пары это бесплатные уроки два указателя с двух концов и окно, которое меняет размер.

Держится именно контраст. Разнесённые на неделю, они и слепились.

Промежутки нужны одному паттерну, а не паре: интервальные повторения.

Честная часть

Твоя матрица будет личной и совсем не похожей на общий список сложных тем.

У меня месяцами рядом стояли кучи и сортировки. Такой пары нет ни в одной программе.

В этом и смысл. Ты собираешь факты о себе. Их меньше, чем кажется.

Где это встроено

AlgoPath ведёт эту матрицу за тебя.

Тренажёр пишет названный паттерн против верного. Спутанные пары приходят чаще.

Первые 33 шага бесплатные.