Давайте решим задачу LeetCode среднего уровня — «Самая длинная подстрока без повторяющихся символов».
Постановка задачи
Решения
Решение проблемы грубой силой состоит в том, чтобы проверить все подстроки с неповторяющимися символами, что будет иметь временную сложность O (n²).
Конечно, мы читаем эту статью не для того, чтобы обсуждать решение методом грубой силы. Попробуем решить постановку задачи эффективным способом.
Позвольте мне призвать вас просто взглянуть на приведенный ниже код и попытаться понять, что происходит, а затем мы углубимся в объяснение.
Идея очень проста,
- Создайте окно, начиная с индекса l и заканчивая индексом r.
- Запишите индекс каждого символа, видимого в окне, на хеш-карте —
seenCharIndex.put(rightChar, r) - Продолжайте расширять окно вправо, пока не встретите символ, который уже является частью окна —
r++ - Как только мы сталкиваемся с символом, который уже является частью окна, сжимаем окно слева до точки, в которой символ находится за пределами окна —
l = Math.max(l, SeenCharIndex.get(rightChar )+ 1) - Запишите максимальную длину окна, просмотренную до сих пор в каждой точке, которая будет возвращена в конце —
ans = Math.max(ans, r -l+1)
Проще говоря, мы расширяем/сжимаем окно, чтобы оно удовлетворяло условию (без повторяющихся символов), и записываем максимальную длину окна.
Обучение
Наша цель не должна состоять только в том, чтобы решить постановку задачи. Скорее мы должны определить, какие концепции мы изучили, чтобы мы могли применять их в будущем.
Такие проблемы подпадают под шаблон или технику, называемую скользящим окном. В этом шаблоне есть два типа окон:
1. Фиксированный размер окна.
2. Гибкий размер окна.
Как мы ясно видим, эта проблема относится к категории гибких размеров окна.
Метод скользящего окна просто интуитивно понятен и очень популярен, поскольку его можно применять для решения множества проблем. Если что-то такое важное и в то же время простое, оно должно быть всегда под рукой. Итак, я призываю вас прочитать эту статью и навсегда закрепить эту концепцию в своем уме.
Спасибо и увидимся в следующем посте. Приятного обучения!
