Добро пожаловать! В сегодняшней статье мы поговорим об алгоритме для решения проблем в широком диапазоне условий, который можно использовать с последовательными данными, такими как строки, массивы и связанные списки: Алгоритм скользящего окна.
Что такое алгоритм скользящего окна?
Происхождение названия этого алгоритма происходит от того, как мы обращаемся с определенной частью структуры данных, как если бы мы смотрели в окно, как вы можете видеть на рисунке выше.
Наиболее важная часть решения проблемы с помощью этого алгоритма заключается в том, что данные, которые необходимо просмотреть в задаче, являются непрерывными.
Возьмем приведенный выше пример: у вас есть массив, и вы пытаетесь найти подмассив с 4 элементами в этом массиве, элементы которого являются смежными и элементы которого имеют наименьшую сумму. Как вы можете решить эту проблему? Первое, что приходит на ум, это путешествие по элементам массива группами по 4 по их индексам вроде 0–1–2–3, 1–2–3–4, 2–3–4–5, … (n -4)-(n-3)-(n-2)-(n-1), чтобы найти то, что имеет наименьшую сумму элементов. Так что же «плохого» в том, чтобы сделать это для решения проблемы? Ответ, конечно же, заключается в временной сложности, и алгоритм вступает в действие именно в этот момент.
Вместо того, чтобы ходить группами по 4 человека один за другим, если мы вычтем 0-й индекс из нашей суммы и добавим следующий элемент в 4-м индексе к нашей новой сумме, как в примере здесь, мы найдем сумму элементов наша новая группа из 4. И мы будем продолжать делать то же самое, пока не достигнем конца массива.
По сути, вы продолжаете складывать и вычитать вместо того, чтобы снова и снова проходить массив. Когда мы закончим это, самое лучшее в этом то, что наша временная сложность теперь составляет O(n).
Мы можем использовать этот алгоритм для нахождения наиболее оптимальных подмассивов массива в нескольких видах задач.
Если вы думаете, что понимаете логику алгоритма, вот вам задание: HackerRank Challenge
До встречи в следующих статьях!
