В этой задаче LeetCode нас просят найти длину самой длинной строки символов в предоставленной строке, которая не содержит повторяющихся символов. Другими словами, в строке hello самой длинной подстрокой без повторяющихся символов является hel (с длиной 3).
Основным методом решения этой проблемы является «движущееся окно», и все нижеприведенные подходы используют его в той или иной форме.
Решение №1: Двойной цикл с набором
Это был мой первый и наименее сложный метод. В нем мы перебираем один раз все символы в предоставленной строке, а затем для каждого из них мы перебираем оставшиеся символы, добавляя каждый в набор, пока не найдем повторяющийся символ. В этот момент мы проверяем, является ли это самой длинной найденной строкой, и сохраняем ее длину, если это так. Это повторяется до конца строки, пока мы не найдем нашу самую длинную подстроку.
Решение № 2: Массив
Это решение похоже на предыдущее, но вместо этого использует массив для хранения текущей строки, которая имеет то преимущество, что она упорядочена и имеет функции splice и indexOf, которые делают это решение особенно удобным для глаз и устраняют необходимость во вложенных петля.
Решение № 3: Карта
Пользователь LeetCode niath разместил это замечательное решение, используя карту, которую я скорректировал, чтобы улучшить читаемость. Он использует концепцию движущегося окна, но использует Карты для молниеносного поиска. Интересно, что поскольку Map представляет собой пару ключ-значение, мы можем использовать букву в качестве ключа, а позицию, которую она занимает в строке, в качестве значения:
Решение № 4: Установите
Это решение было вдохновлено решением jeantimex для Java и основано на концепции карты, но немного упрощает работу, чтобы вместо этого использовать набор. Это дает преимущество в уменьшении сложности кода, но, возможно, ухудшает читабельность:
Сравнение решений
Все подходы (за исключением двойного цикла) имеют одинаковую производительность и различаются между тестами настолько, что ими можно пренебречь:
Однако интересно то, что процессор LeetCode настолько оптимизирован для работы с массивами, что если вы начнете все эти подходы с первого преобразования строки в массив (используя string.split('')), вы увидите прирост производительности по всем направлениям.
