Определение длины наибольшего подмассива без дублирующихся элементов

Условие

Реализуйте функцию, принимающую массив, и вычисляющую максимальную длину непрерывного подмассива, в котором все элементы уникальны. Пример сигнатуры функции:

def longest_unique_subarray(arr: List[int]) -> int:
    # ваш код здесь

Функция должна вернуть единственное число — длину самого длинного отрезка массива, где нет повторяющихся значений.

Ответ

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

def longest_unique_subarray(arr):
    last = {}
    left = best = 0
    for right, value in enumerate(arr):
        if value in last:
            left = max(left, last[value] + 1)
        last[value] = right
        best = max(best, right - left + 1)
    return best

Для пустого массива ответ 0, для одинаковых элементов — 1. Повтор за пределами текущего окна его не сокращает. В среднем время O(n), дополнительная память O(u), где u — число различных значений.