Ctrl K

Отрезки с достаточным числом совпадений

Средняя
Дан массив целых чисел values и число need. В отрезке массива *совпадение* — это пара позиций i < j внутри него, где values[i] == values[j]. Например, в [5, 5, 5] три совпадения. Посчитайте, сколько непрерывных непустых отрезков values содержат не меньше need совпадений.
Пример 1
values=[2, 7, 2, 7], need=2 → 1

Только во всём массиве две пары совпадений: двойки на 0 и 2, семёрки на 1 и 3.

Пример 2
values=[4, 4, 4], need=1 → 3

Подходят [4, 4] (дважды, на разных местах) и [4, 4, 4] с тремя парами.

Пример 3
values=[1, 2, 3], need=1 → 0
Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁹
  • 1 ≤ need ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОтрезок плейлиста из двух жанров СредняяОкна с заданным числом тревог СредняяОтрезки с k нечётными СредняяДва отрезка с нужной суммой СредняяСнять с краёв ровно столько Средняя
загружаем Python…
Вход
values=[2, 7, 2, 7], need=2
Ожидается
1

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 119 тестов на сервере, включая скрытые.