Войти Регистрация
Алгоритмы

183. Кратчайший отрезок просмотров со всеми рубриками

Средняя

В журнале сессии Авито views[i] — рубрика i-го просмотренного объявления, например "авто" или "шины".

Список need — рубрики, которые должны встретиться в отрезке; повтор в need значит, что рубрика нужна столько же раз.

Верните длину самого короткого отрезка подряд идущих просмотров, где все рубрики из need есть в нужном количестве. Если такого отрезка нет, верните 0.

В работе: Рекомендации ищут, за сколько просмотров человек сравнил авто, шины и диски: в сессии 4000 просмотров, перебор всех отрезков — 8 млн проверок на сессию.

Пример 1

Ввод
views = ["авто", "шины", "одежда", "диски", "авто", "шины"]
need = ["авто", "шины", "диски"]
Вывод
3

Отрезок «диски, авто, шины» — 3 просмотра.

Пример 2

Ввод
views = ["шины", "шины", "авто"]
need = ["шины", "шины", "шины"]
Вывод
0

Шин нужно три, есть только две.

Ограничения

  • 1 ≤ длина views ≤ 10⁵
  • 1 ≤ длина need ≤ 10⁵
  • рубрика — непустая строка до 20 символов
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def shortest_session(views, need):
Скользящее окноХеш-таблицаПодсчётцельO(n)

Источник: наша задача на данных Авито. Условие пересказано своими словами.