É tudo uma questão de padrões!

Depois de aprender os padrões, tudo começa a ficar um pouco mais fácil! Se você é como eu, provavelmente não gosta de entrevistas técnicas e não culpo você - elas podem ser difíceis.

Problemas de array são alguns dos mais comuns que você encontrará em entrevistas. Esses problemas geralmente envolvem trabalhar com matrizes naturais:

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

E problemas de strings, que são essencialmente matrizes de caracteres:

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

Um dos padrões mais comuns para resolver problemas de array é a janela deslizante.

Padrão de janela deslizante

O padrão de janela deslizante envolve dois ponteiros que se movem na mesma direção, como uma janela deslizando pela matriz.

Quando usar

Use o padrão de janela deslizante quando precisar encontrar uma submatriz ou substring que satisfaça uma determinada condição, como ser o mínimo, máximo, mais longo ou mais curto.

Regra 1: Se você precisar encontrar uma submatriz ou substring e a estrutura de dados for uma matriz ou string, considere usar o padrão de janela deslizante.

Exemplo simples

Aqui está um exemplo básico para introduzir o conceito de ponteiros em uma janela deslizante:

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

    while (r 



Observe que os ponteiros esquerdo (L) e direito (R) não precisam se mover ao mesmo tempo, mas devem se mover na mesma direção.



O ponteiro direito nunca será inferior ao ponteiro esquerdo.

Vamos explorar esse conceito com um problema de entrevista real.


  
  
  Problema do mundo real: substring mais longa sem repetição de caracteres


Problema: Dada uma string s, encontre o comprimento da substring mais longa sem repetir caracteres.

Palavras-chave: substring, mais longa (máximo)


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;
}




Não se preocupe se isso parecer complicado – veremos isso pouco a pouco.


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




O núcleo deste problema é encontrar a substring mais longa sem caracteres repetidos.


  
  
  Janela Inicial: Tamanho 0


No início, os ponteiros esquerdo (L) e direito (R) estão no mesmo lugar:


let left = 0;

for (let right = 0; right 





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




E temos um hash vazio (objeto):


let hash = {};




O que há de bom nos objetos? Eles armazenam chaves exclusivas, que é exatamente o que precisamos para resolver esse problema. Usaremos hash para rastrear todos os personagens que visitamos e verificar se já vimos o personagem atual antes (para detectar duplicatas).

Olhando para a string, podemos dizer visualmente que world é a substring mais longa sem repetir caracteres:


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




Isso tem comprimento 5. Então, como chegamos lá?

Vamos detalhar passo a passo:


  
  
  Estado inicial




hash = {}

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





  
  
  Iteração 1:


Em cada iteração, adicionamos o caractere sob o ponteiro R ao mapa hash e incrementamos:


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




Atualmente, não há caracteres repetidos em nossa janela (h e e):


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





  
  
  Iteração 2:




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




Agora, temos uma nova janela: hel.


  
  
  Iteração 3:




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




É aqui que fica interessante: já temos l em nosso hash e R está apontando para outro l na string. É aqui que entra nossa instrução if:


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




Se nosso hash contiver a letra R para a qual está apontando, encontramos uma duplicata! A janela anterior (hel) é a mais longa até agora.

Então, o que faremos a seguir? Reduzimos a janela da esquerda movendo o ponteiro L para cima, pois já processamos a substring esquerda. Mas até onde nos movemos L?


left = hash[str[right]]   1;




Movemos L para logo após a duplicata:


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




Ainda adicionamos nossa duplicata ao hash, então L agora terá um índice de 3.


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





  
  
  Novo Estado: Iteração 4




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





  
  
  Iterações 4 a 6




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




Quando R aponta para outra duplicata (o), movemos L para logo após o primeiro o:


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




Continuamos até encontrarmos outra duplicata 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




Mas observe que está fora da janela atual! começando em w, 


  
  
  Regra 3: Ignorar sub-x processado


Qualquer coisa fora da janela atual é irrelevante – já processamos isso. O código-chave para gerenciar isso é:


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




Esta condição garante que nos preocupamos apenas com os caracteres dentro da janela atual, filtrando qualquer ruído.


hash[str[right]] >= left




Nós nos concentramos em qualquer coisa maior ou igual ao ponteiro esquerdo


  
  
  Iteração Final:




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




Eu sei que isso foi detalhado, mas dividir os problemas em padrões ou regras menores é a maneira mais fácil de dominá-los.


  
  
  Resumindo:

• Regra 1: Palavras-chave no problema (por exemplo, máximo, mínimo) são pistas. Este problema é encontrar a substring mais longa sem caracteres repetidos.
• Regra 2: Se você precisar encontrar elementos únicos ou não repetitivos, pense em mapas hash.
• Regra 3: Concentre-se na janela atual – qualquer coisa fora dela é irrelevante.

Dicas bônus:

• Divida o problema e torne-o detalhado usando um pequeno subconjunto.
• Ao maximizar a janela atual, pense em como torná-la o mais longa possível. Por outro lado, ao minimizar, pense em como torná-lo o menor possível.

Para encerrar, aqui está um pequeno desafio para você experimentar! Vou postar minha solução nos comentários – é uma ótima maneira de praticar.

Problema 2: Soma maior ou igual à meta

Dado um array, encontre o menor subarray com uma soma igual ou maior que o alvo (minha solução será o primeiro comentário).

/**
 * 
 * @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!
}

Lembre-se, como qualquer coisa na programação, a repetição é fundamental! Problemas com janelas deslizantes surgem o tempo todo, então não hesite em procurar mais exemplos no Google e continue praticando.

Estou sendo breve, mas fique atento - o próximo artigo se aprofundará no padrão de dois ponteiros e na recursão (preparação para problemas de árvore). Vai ser um pouco mais desafiador!

Se quiser mais conteúdo exclusivo, pode me seguir no Twitter ou no Ko-fi que estarei postando algumas coisas extras lá!

Recursos:

Manual de entrevista técnica

matrizes de código leet 101