Два указателя, без таблицы
Почему это важно У задачи "найдите две вещи, которые в сумме дают X" есть знаменитый ответ: положить всё в множество и искать пару. Это быстро, но нужна копия всех данных. Когда данные отсортированы, памяти не нужно почти совсем.
Подарочный сервис продаёт наборы из двух разных товаров по фиксированной цене набора. Прайс-лист товаров отсортирован, без повторов и лежит на встроенном устройстве с очень небольшим количеством свободной памяти. Для цены набора нужно число пар товаров, цены которых в сумме дают ровно эту цену.
prices = [1, 2, 3, 4, 5, 6] # sorted, no repeats
count_pairs(Tape(prices), 7) # 3: (1, 6), (2, 5), (3, 4)Напишите count_pairs(tape, target). tape - это Tape целочисленных цен, отсортированных по возрастанию, без повторов. Верните, сколько пар из двух разных товаров дают в сумме ровно target (каждая пара считается один раз). Бюджеты: для 20 000 товаров прочитать не больше 60 000 значений и использовать не больше 16 000 байт рабочей памяти, пока работает функция (измеряется через tracemalloc; множество или список из 20 000 цен - больше 150 000 байт). len(tape) бесплатен.
Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке
Это упражнение откроется скоро
Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.
Этот браузер блокирует cookies для learn.floati.life, поэтому завершенные здесь уроки не могут открыться по порядку. Разрешите cookies для этого сайта и перезагрузите страницу.