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

199. Отрезки выдачи ровно с k продавцами

Средняя

Выдача Wildberries по запросу — список карточек, sellers[i] — номер продавца i-й карточки.

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

В работе: Команда поиска меряет разнообразие выдачи: на экране телефона 6–10 карточек подряд, и доля отрезков ровно с 1–2 продавцами показывает, где один магазин занял полэкрана.

Пример 1

Ввод
sellers = [7, 3, 7, 3, 5]
k = 2
Вывод
7

Отрезки с двумя продавцами: [7,3], [3,7], [7,3], [7,3,7], [3,7,3], [7,3,7,3], [3,5] — 7 штук.

Пример 2

Ввод
sellers = [4, 4, 4]
k = 1
Вывод
6

Все шесть отрезков из одного продавца.

Ограничения

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

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