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

12. Сколько подмассивов без повторов

Средняя

Дан массив целых чисел arr. Посчитайте, сколько у него непрерывных подмассивов, в которых все значения различны.

Подмассивы с одинаковым содержимым, но в разных местах, считаются отдельно.

В работе: Сколько отрезков плейлиста можно включить подряд, чтобы трек не повторился.

Пример 1

Ввод
arr = [1, 2, 1]
Вывод
5

[1], [2], [1], [1, 2], [2, 1] — пять; [1, 2, 1] не подходит.

Пример 2

Ввод
arr = [4, 4]
Вывод
2

Ограничения

  • 0 ≤ длина arr ≤ 10⁶
  • Ответ может быть больше 2³¹ — в JavaScript он помещается в Number до 2⁵³
  • Лимит — 1 с на тест.
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def count_distinct_subarrays(arr):
Скользящее окноХеш-таблицацельO(n)

Источник: Яндекс Образование, 2024. Условие пересказано своими словами.

Давали на собеседовании? Ответов пока мало — ваш поможет.