Пара с суммойLeetCode 167
Дан массив цен, отсортированный по возрастанию, и сумма сертификата. Найдите два разных товара, которые вместе стоят ровно эту сумму, и верните их индексы. Дополнительная память — O(1).
Алгоритмы на массивах · модуль 8 · два указателя
Глава 8.2
Формулировки задач
и признаки техники
В этой главе разобрано, как звучит задача на два указателя: из каких частей состоит условие, какие слова в нём подсказывают технику и в каких случаях похожая задача решается по-другому. Восемь формулировок с собеседований размечены по признакам, в конце — тренажёр: по условию выбрать технику.
- Категория
- Работа с условием
- Уровень
- Начальный
- Опирается на
- Глава 8.1: три формы техники
- Зачем это знать
- Узнавать технику по условию до того, как писать код
§1Из чего состоит условие
Условие задачи на собеседовании обычно короткое, и в нём четыре части. Легенда объясняет, откуда данные: цены товаров, идентификаторы заказов, показания датчика. Входные данные — что передаётся в функцию. Результат — что вернуть. Ограничения — по времени, по памяти, можно ли менять вход. Технику подсказывают три последние части. Легенду можно заменить любой другой, и решение от этого не изменится.
Как звучитВ интернет-магазине есть каталог, цены в нём отсортированы по возрастанию. У покупателя подарочный сертификат на сумму
target. Найдите два разных товара, которые вместе стоят ровно столько. Дополнительную память используйте O(1).→
Что это значитВход: отсортированный список чисел и число. Результат: пара индексов
i < j с суммой target или None. Ограничения: список не копировать, словарь не заводить.Легендамагазин, сертификат, покупатель
→
Для решения не нужнаТа же задача про два платежа, которые вместе дают сумму из выписки, решается тем же кодом.
Признаки«отсортированы по возрастанию», «два», «ровно», «O(1)»
→
Что подсказываютПара из отсортированного списка без дополнительной памяти — указатели навстречу.
§2Восемь формулировок
Ниже восемь условий в том виде, в каком их формулируют на интервью: без подсказки, какую технику применить. Это пересказы задач LeetCode, ссылка — в шапке карточки. Кнопка под карточками подсвечивает слова, по которым узнаётся техника.
ПовторыLeetCode 26
Дан отсортированный список идентификаторов заказов, в нём есть повторы. Удалите повторы на месте и верните число оставшихся значений.
СжатиеLeetCode 443
Дан массив символов. Замените каждую серию одинаковых символов подряд на символ и длину серии. Результат запишите в тот же массив и верните новую длину.
Нули в конецLeetCode 283
Перенесите все нули в конец массива, сохранив порядок остальных элементов. Копию массива создавать нельзя.
ПалиндромLeetCode 125
Строка — палиндром, если, оставив в ней только буквы и цифры без учёта регистра, её можно прочитать одинаково слева направо и справа налево. Проверьте строку.
СлияниеLeetCode 88
Даны два отсортированных массива. Объедините их в один отсортированный массив.
КвадратыLeetCode 977
Массив отсортирован по возрастанию и содержит отрицательные числа. Верните массив квадратов его элементов, тоже по возрастанию, за O(n).
Три цветаLeetCode 75
Массив состоит из чисел 0, 1 и 2. Расставьте их по возрастанию за один проход, на месте и без встроенной сортировки.
§3Признаки в условии
Подсвеченные слова повторяются от задачи к задаче. Таблица собирает их вместе. Одного признака мало: технику выбирают по сочетанию признаков.
| Слова в условии | Что они сообщают | Какая форма |
|---|---|---|
| «отсортирован», «по возрастанию», «по неубыванию» | Сравнение с целью показывает, в какую сторону двигаться: слева значения меньше, справа больше | навстречу |
| «пара», «два элемента», «сумма двух» | Ответ — два элемента; перебор всех пар стоит O(n²) | навстречу, если есть порядок |
| «на месте», «без копии», «в том же массиве», «память O(1)» | Результат пишется в тот же список, новый не создаётся | в одну сторону: чтение и запись |
| «верните новую длину», «верните число оставшихся» | Ответ — первые k элементов списка, остальное не важно | в одну сторону |
| «подряд», «серия», «соседние» | Решение зависит от элементов, идущих друг за другом | в одну сторону |
| «с двух концов», «палиндром», «симметрично», «развернуть» | Элементы сравниваются парами: первый с последним, второй с предпоследним | навстречу |
| «два отсортированных массива», «объедините» | Данные в двух упорядоченных источниках | по двум спискам |
| «за один проход», «O(n)», «без встроенной сортировки» | Перебор пар и сортировка O(n log n) не проходят по ограничению | любая, но перебор исключён |
§4Когда техника не подходит
Указателям навстречу нужен порядок в данных, указателям в одну сторону — чтобы решение по каждому элементу принималось один раз. Если требование не выполнено, нужна другая техника.
УсловиеНайдите два числа с заданной суммой. Массив не отсортирован, вернуть нужно исходные индексы.
РешениеУказатели навстречу требуют порядка, а сортировка перемешает индексы. Подходит словарь уже просмотренных чисел: O(n) по времени и O(n) по памяти. Это LeetCode 1 Two Sum, хеш-таблицы — занятие 17.
УсловиеНайдите число подотрезков с суммой ровно S. В массиве есть отрицательные числа.
РешениеПри сдвиге правой границы сумма может и вырасти, и уменьшиться, поэтому нельзя решить, какую границу двигать. Решают префиксными суммами со словарём — занятие 11.
УсловиеВерните все пары с суммой S, если их может быть много.
РешениеУказатели работают, но после найденной пары двигаются дальше, а повторы значений пропускаются отдельно. Время остаётся O(n) плюс размер ответа. Такой проход работает внутри задачи 3Sum.
На полях: отсортировать самим
Если вход не отсортирован, но индексы в ответе не нужны — достаточно самих значений, — его можно отсортировать и применить указатели. Сортировка стоит O(n log n), и это время добавляется к решению.
§5Тренажёр: выберите технику
Ниже шесть условий. Для каждого выберите способ, который подходит при указанных ограничениях и работает быстрее остальных вариантов. В вариантах — перебор, три формы двух указателей и встроенные средства Python: set, sorted, срез. После ответа открывается разбор верного и выбранного вариантов.
Условие 1Температуры за месяц записаны по дням. Проверьте, есть ли два разных дня, сумма температур в которых равна 40, и верните номера дней. Список менять нельзя.
Температуры записаны по дням и по возрастанию не упорядочены. Без порядка сумма крайних элементов не показывает, какой указатель двигать, и пара может быть пропущена.
Верно, из этих трёх способов подходит только перебор: он не требует порядка и не меняет список. Время O(n²). Для неотсортированного входа есть и более быстрый способ — словарь просмотренных значений.
Чтение и запись нужны, когда список изменяется на месте. Здесь его менять нельзя, а ответ — пара номеров.
Условие 2Список номеров билетов отсортирован по возрастанию, некоторые номера продублированы при выгрузке. Уберите повторы в том же списке и верните количество различных номеров.
Верно.
rчитает каждый номер,wуказывает место для следующего нового. Повторы в отсортированном списке стоят рядом, поэтому хватает сравнения с последним записанным.Навстречу ищут пару с двух концов. Здесь каждый элемент нужно сравнить с предыдущим оставленным, по порядку.
Условие требует работать в том же списке. Кроме того,
setне сохраняет порядок.Сравнивать каждый номер с каждым не нужно: одинаковые номера в отсортированном списке стоят подряд.
Условие 3Даны два списка с временем событий из двух журналов, каждый отсортирован. Получите общий отсортированный список событий.
Решение верное, но стоит O((n + m) log (n + m)) и не использует того, что оба списка уже отсортированы.
Склеенный список не отсортирован целиком, а указатели навстречу ищут пару и порядок не строят.
Верно. На каждом шаге в ответ идёт меньший из двух текущих элементов, и его указатель сдвигается. Время O(n + m).
Условие 4Расстояния от склада до пунктов выдачи отсортированы по возрастанию. Курьер может проехать ровно 300 км. Найдите два пункта, расстояния до которых в сумме дают 300, и верните их номера. Дополнительная память — O(1).
Список не нужно менять, нужна пара элементов. Чтение и запись здесь ничего не дают.
Перебор даст верный ответ, но за O(n²). Расстояния отсортированы, поэтому есть способ за O(n).
Верно. Это задача 1 модуля с другой легендой: отсортированный вход, пара с заданной суммой, память O(1).
Условие 5Проверьте, что пароль, записанный как список символов, читается одинаково с обоих концов. Копию списка создавать нельзя.
Верно. Первый символ сравнивается с последним, второй с предпоследним; указатели сходятся к середине. Время O(n), память O(1).
Срез
s[::-1]создаёт копию, а условие это запрещает.Список не нужно менять. Нужно сравнить элементы парами с двух концов.
Условие 6Отменённые заказы в списке помечены нулём. Перенесите их в конец, сохранив порядок остальных заказов. Новый список не создавать.
Обмены с двух концов переставят заказы, и исходный порядок не сохранится. Этот вариант подходит, когда порядок не важен.
Устойчивая сортировка сохранит порядок, но стоит O(n log n), а задача решается за O(n).
Верно.
wуказывает место для следующего неотменённого заказа, обмен сrуводит нули назад. Порядок оставшихся не меняется.
Модуль 8 · Два указателя · ОП.04 · 3 курс