Подсчитайте подмассивы, содержащие не менее k пар дубликатов. ⇐ C++

[Anonymous]

Здравствуйте, программисты!

Код: Выделить всё

I encountered this question in an interview:

Задача: вам дан массив целых чисел и положительное целое число k. Ваша задача — подсчитать количество смежных подмассивов в числах, содержащих не менее k пар элементов с повторяющимися значениями.
Примеры:
nums = [1, 0, 1, 0, 1] и k = 2
Решение – 3, а именно:

Код: Выделить всё

[1, 0, 1, 0]
[0, 1, 0, 1]
[1, 0, 1, 0, 1]
These subarrays have at least 2 pairs of elements which are (0, 1).
nums = [2, 2, 2, 2, 2, 2] and k = 3
The solution is 1.

Сначала я решил эту проблему с помощью грубой силы, и меня частично приняли. Однако им нужно решение с линейной временной сложностью.
С уважением,

Подробнее здесь: https://stackoverflow.com/questions/788 ... duplicates