Все дело в шаблонах!

Как только вы изучите шаблоны, все станет немного проще! Если вы похожи на меня, вам, вероятно, не нравятся технические интервью, и я вас не виню — они могут быть трудными.

Проблемы с массивами — одни из наиболее распространенных, с которыми вы можете столкнуться на собеседованиях. Эти проблемы часто связаны с работой с естественными массивами:

const arr = [1, 2, 3, 4, 5];

И проблемы со строками, которые по сути представляют собой массивы символов:

"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']

Одним из наиболее распространенных шаблонов решения проблем с массивами является скользящее окно.

Раздвижное окно

Шаблон скользящего окна включает в себя два указателя, которые перемещаются в одном направлении — как окно, скользящее по массиву.

Когда его использовать

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

Правило 1: Если вам нужно найти подмассив или подстроку, а структура данных представляет собой массив или строку, рассмотрите возможность использования шаблона скользящего окна.

Простой пример

Вот базовый пример, демонстрирующий концепцию указателей в скользящем окне:

function SlidingWindow(arr) {
    let l = 0;  // Left pointer
    let r = l   1;  // Right pointer

    while (r 



Обратите внимание, что указатели влево (L) и вправо (R) не обязательно должны перемещаться одновременно, но они должны двигаться в одном направлении.



Правый указатель никогда не будет ниже левого указателя.

Давайте рассмотрим эту концепцию на примере реальной задачи на собеседовании.


  
  
  Реальная проблема: самая длинная подстрока без повторяющихся символов


Задача: Дана строка s, найти длину самой длинной подстроки без повторяющихся символов.

Ключевые слова: под-строка, самая длинная (максимум)


function longestSubstr(str) {
    let longest = 0;
    let left = 0;
    let hash = {};

    for (let right = 0; right = left) {
            left = hash[str[right]]   1;
        }

        hash[str[right]] = right;
        longest = Math.max(longest, right - left   1);
    }

    return longest;
}




Не волнуйтесь, если это покажется сложным — мы разберемся с этим постепенно.


let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5




Суть этой проблемы заключается в поиске самой длинной подстроки без  повторяющихся символов.


  
  
  Начальное окно: Размер 0


В начале левый (L) и правый (R) указатели находятся в одном месте: 


let left = 0;

for (let right = 0; right 





h e l l o w o r l d 
^
^
L
R




И у нас есть пустой хеш (объект):


let hash = {};




Что хорошего в объектах? В них хранятся уникальные ключи, а это именно то, что нам нужно для решения этой проблемы. Мы будем использовать хеш для отслеживания всех посещенных нами персонажей и проверки, видели ли мы текущего персонажа раньше (для обнаружения дубликатов).

Глядя на строку, мы можем визуально сказать, что world — это самая длинная подстрока без повторяющихся символов:


h e l l o w o r l d 
          ^        ^   
          L        R




Длина этого значения равна 5. Итак, как нам туда добраться?

Давайте разберем это шаг за шагом:


  
  
  Исходное состояние




hash = {}

h e l l o w o r l d 
^
^
L
R





  
  
  Итерация 1:


На каждой итерации мы добавляем символ под указателем R в хеш-карту и увеличиваем:


hash[str[right]] = right;
longest = Math.max(longest, right - left   1);




На данный момент в нашем окне нет повторяющихся символов (h и e):


hash = {h: 0}
h e l l o w o r l d 
^ ^
L R





  
  
  Итерация 2:




hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R




Теперь у нас появилось новое окно: хел.


  
  
  Итерация 3:




hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R




И вот что интересно: в нашем хэше уже есть l, а R указывает на другую l в строке. Вот тут-то и пригодится наш оператор if:


if (hash[str[right]] !== undefined)




Если наш хэш содержит букву, на которую указывает R, мы нашли дубликат! Предыдущее окно (hel) на данный момент является нашим самым длинным.

Итак, что нам делать дальше? Мы сжимаем окно слева, перемещая указатель L вверх, поскольку мы уже обработали левую подстроку. Но как далеко мы переместим L?


left = hash[str[right]]   1;




Мы перемещаем букву L сразу после дубликата:


hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R




Мы по-прежнему добавляем наш дубликат в хэш, поэтому индекс L теперь будет равен 3.


hash[str[right]] = right;
longest = Math.max(longest, right - left   1);





  
  
  Новое состояние: итерация 4




hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R





  
  
  Итерации с 4 по 6




hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R




Когда R указывает на другой дубликат (o), мы перемещаем L сразу после первого o:


hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R




Продолжаем, пока не встретим еще один дубликат l:


hash = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^     ^
          L     R




Но обратите внимание, что оно находится за пределами текущего окна! начиная с w, 


  
  
  Правило 3: игнорировать обработанный суб-x


Все, что находится за пределами текущего окна, не имеет значения — мы это уже обработали. Ключевой код для управления этим: 


if (hash[str[right]] !== undefined && hash[str[right]] >= left)




Это условие гарантирует, что мы заботимся только о символах в текущем окне, отфильтровывая любой шум.


hash[str[right]] >= left




Мы фокусируемся на чем-то большем или равном левому указателю


  
  
  Финальная итерация:




hash = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^       ^
          L       R




Я знаю, что это было подробно описано, но разбиение проблем на более мелкие закономерности или правила — самый простой способ их освоить.


  
  
  В итоге:

• Правило 1: Ключевые слова в задаче (например, максимум, минимум) являются подсказками. Эта проблема заключается в поиске самой длинной подстроки без повторяющихся символов.
• Правило 2: Если вам нужно найти уникальные или неповторяющиеся элементы, подумайте о хеш-картах.
• Правило 3: Сосредоточьтесь на текущем окне — все, что за его пределами, не имеет значения.

Бонусные советы:

• Разбейте проблему и сделайте ее подробной, используя небольшое подмножество.
• При развертывании текущего окна подумайте о том, как сделать его максимально длинным. И наоборот, сворачивая, подумайте о том, как сделать его как можно меньшим.

В заключение, вот вам небольшое задание! Я опубликую свое решение в комментариях — это отличный способ попрактиковаться.

Задача 2: сумма больше или равна целевой

Давный массив, найдите наименьший подмассив с суммой, равной или большей целевой (мое решение будет первым комментарием).

/**
 * 
 * @param {Array} arr 
 * @param {number} target 
 * @returns {number} - length of the smallest subarray
 */
function greaterThanOrEqualSum(arr, target){
   let minimum = Infinity;
   let left = 0;
   let sum = 0;

   // Your sliding window logic here!
}

Помните, что, как и во всем в программировании, повторение является ключевым моментом! Проблемы со скользящим окном возникают постоянно, так что не стесняйтесь искать в Google дополнительные примеры и продолжайте практиковаться.

Я буду краток, но следите за обновлениями — следующая статья будет посвящена шаблону двух указателей и рекурсии (подготовка к проблемам с деревьями). Это будет немного сложнее!

Если вам нужен более эксклюзивный контент, вы можете подписаться на меня в Твиттере или Ko-fi, я буду публиковать там еще кое-что!

Ресурсы:

Справочник по собеседованиям в сфере технологий

массивы кода 101