Este patrón como su nombre indica se basa en "mover una ventana", es decir, tratamos con los datos que estan dentro de esa ventana ignorando el resto, y vamos deslizando la ventana con los siguientes datos.
Veamoslo con un ejemplo. Dentro de un array queremos obtener la suma mayor entre "n" de esos números consecutivos, es decir, si por ejemplo queremos saber cual es la suma mayor de 2 números consecutivos de este array:

[1,4,2,6,3,9]

Tendremos que sumar:

  • 1 + 4
  • 4 + 2
  • 2 + 6
  • 6 + 3
  • 3 + 9

Por eso he comentado que es como mover una ventana o una caja donde solo entran 2 números y sumamos cada vez que cambia uno de los números.

Veamos el posible acercamiento mas habitual o sencillo (el que solemos hacer primero) aunque sería el más lento

// arr: el array a comprobar
// num: número de elementos en el subarray, de cuantos números queremos realizar el cálculo
function maxSubarraySum (arr, num){
    if (num > arr.length) return null;
    
    var max = -Infinity;
    for(let i = 0; i < arr.length - num + 1; i++){
        temp = 0;
        for (let j = 0; j < num; j++){
            temp += arr[i+j];
        }
        if (temp > max) {
            max = temp;
        }
    }
    return max;
}

Como vemos tenemos un "nested loop", y lo que hacemos es recorrer cada número en el primer loop y en el segundo sumamos los "n" números siguientes.

Es relativamente fácil pero tenemos una complejidad temporal de O(n^2)

Ahora veamos como sería usando el Sliding Pattern

function maxSubarraySum (arr, num){
    let maxSum = 0;
    let tempSum = 0;

    if (arr.length < num) return null;

    for (let i = 0; i < num; i++){
        maxSum += arr[i];
    }

    tempSum = maxSum;

    for (let i = num; i < arr.length; i++){
        const leftLeg = arr[i - num];
        const rightLeg = arr[i];
        tempSum = tempSum - leftLeg + rigthLeg;  
        maxSum = Math.max(tempSum, maxSum);
    }

    return maxSum;
}

Esto ya tiene algo más de "chicha", así que vayamos por partes

for (let i = 0; i < num; i++){
   maxSum += arr[i];
}
 tempSum = maxSum;

Sumamos los números que estarían inicialmente en la ventana, es decir desde "n" hasta 0 y lo establecemos en una variable que usaremos de comodín para ir moviéndonos (tempSum)

 for (let i = num; i < arr.length; i++){
     const leftLeg = arr[i - num];
     const rightLeg = arr[i];
     tempSum = tempSum - leftLeg + rigthLeg;   
     maxSum = Math.max(tempSum, maxSum);
 }

A continuación recorremos empezando por "n", es decir, después de sumar los "n" primeros números, y el paso sería elimino el primero y añado el siguiente, (para clarificar con el ejemplo de la ventana he creado leftLeg como limite o pata izquierda de la ventana y rightLeg como el derecho ) siendo más específico lo que hacemos es restarle a tempSum el primer número dentro de nuestra "ventana o cajón", que seria leftLeg y le añadimos el siguiente que esté fuera, es decir rightLef. Y vamos comparando con el valor anterior y metiendo el mayor dentro de la variable maxTemp

Siguiendo con el ejemplo de antes con este array, usando 2 valores consecutivos:

[1,4,2,6,3,9]

Los pasos serían:

  • En el primer loop, se suman los 2 primeros, con un resultado de 5 y se asigna a la variable tempSum.
  • En el segundo loop se le resta a tempSum el 1, se le suma 2, lo que nos daría 6 y así sucesivamente
  • 6 - 4 + 6
  • 8 - 2 + 3
  • 9 - 6 + 9
  • Lo que nos daría 12

Otro ejemplo algo más complicado.

En este caso la idea es encontrar el mínimo número de elementos necesarios del array que su suma sea igual o superior al número dado. Veamoslo con números primero, tenemos este array:

[2,1,6,5,4]

Y queremos saber cual es la menor cantidad de números de ese array que su suma sea igual o mayor que 9. En este caso serian necesarios 2 números (5+4).

Antes de ver el ejemplo, os cuento lo que haremos:

  1. En este caso empezaremos a sumar desde 0, creando nosotros la ventana, hasta que la suma sea mayor o igual que el número que buscamos.
  2. Cuando la suma sea mayor o igual veremos cuantos números hemos necesitado, lo apuntaremos y empezaremos a mover la ventana (recordar restando el primer número y sumando el siguiente)
function minSubArrayLen(nums, sum){
    let total = 0;
    let start= 0;
    let end = 0;

    let minLen = Infinity;

    while (start < nums.length) {
        //Si la ventana actual no es mayor o igual que el número dado movemos la ventana a la derecha, es decir ampliamos la ventana
        if (total < sum && end < nums.length){
            total += nums[end];
            end++;
        } 
        //Si la ventana actual suma al menos la suma dada entonces podemos reducir la ventana
        else if(total >= sum){
            minLen = Math.min(minLen, end - start);
            total -= nums[start];
            start++;
        } //Si el total actual es menor que lo que necesitamos pero hemos llegado al final, necesitamos el break para no un infinite loop
        else {
            break;
        }
    }

    return minLen === Infinity ? 0 : minLen;
    
}

Otro ejemplo más

En este caso queremos contar los carácteres del substring mas largo con carácteres distintos, es decir, buscamos un substring sin que se repita ninguna letra. Aquí usaremos una mezcla entre el frequency counter y el sliding pattern. Básicamente iremos anotando las letras por las que pasamos e ir moviendo la window según se repitan

function findLongestSubstring(str) {
  let longest = 0;
  let seen = {};
  let start = 0;
 
  for (let i = 0; i < str.length; i++) {
		let char = str[i];
    //Comprobamos si ya lo tenemos, y si existe, nuestro start seria el que tenemos anotado ya
    if (seen[char]) {
			start = Math.max(start, seen[char]);
    }
		// Sumamos uno para tener en cuenta el caracter actual
    longest = Math.max(longest, i - start + 1);
		// guardamos el índice con el siguiente carácter si se repite no contarlo, el nuevo esta dentro
		// de la ventana
		seen[char] = i + 1;
  }
  return longest;
}

Este ejemplo es algo más díficil de entender, creo que sobretodo el moviento de la ventana, por explicarlo un poco más supongamos que queremos saber la cantidad de caracteres máximo consecutivo donde no se repite ningún caracter de la palabra ninja (como no...), el resultado sería 4 pero veamos un poco el flujo hasta que cambia (tengamos en cuenta que i y start son las "patas" de la ventana):

  • Empieza siendo i 0 por lo que empezamos con la n, como no tenemos nada guardado todavía dentro de seen la variable start se queda con 0, longest sería 1 (tanto i como start son 0) y se guardaría seen.n = 1
  • A continuación la i del index es 1, lo que hace que la siguiente letra sea la i. No existe todavía dentro de seen por lo que start todavía seguiría siendo 0, longest pasaría a ser 2 (i es 1 y start 0) y guardamos seen.i = 2
  • En la siguiente iteración la i del index es 2, por lo que la siguiente letra es n. En este caso si que tenemos coincidencia dentro seen por lo que start pasaría a ser 1. Aquí es donde está la parte algo más complicada de ver al principio, este paso es el porqué de guardar cada letra con un +1 dentro de seen. Para explicarlo pensemos en el concepto de la ventana, antes de pasar por la modificación del start tenemos que el borde izquierdo (la posición actual del start) esta en la posición 0 y el borde derecho (la i) está en la posición 2, al encontrar coincidencía lo que tenemos que hacer es mover la posición del borde izquierdo para sacar la n de nuestro rango de la ventana por lo que para sacarla sería mover la posición actual del borde izquierdo a n + 1, es decir, movernos al siguiente carácter. Nuestra ventana ahora pasa de estar en nin a in. Hemos movido el start de 0 a 1 por lo que en este caso si la i es 2 entonces longest sigue siendo 2 y ahora como ya existe la n dentro seen pasamos a tener seen.n = 3
  • Ahora la i del index es 3, por lo que la siguiente letra es j, como no hemos pasado por ninguna nuestro start no cambia sigue en 1, longest ahora pasaría a ser 3 (i es 3, start es 1) y guardariamos seen.j = 4
  • Por último la i del index es 4, por lo que ya estariamos en la última letra que es la a, como no tenemos ninguna start sigue siendo 1, longest ahora pasaría a ser 4 (i es 4 y start es 1) y por último se guardaría seen.a = 5

En este punto terminaría la ejecución y nos devolvería longest que sería 4, es decir, inja. En este ejemplo lo más importante es ver como se mueve la ventana realmente, que lo que hace es ir creciendo hasta que encuentra una repetición y coloca su start a continuación de la repetición para comenzar de nuevo sin incluir ese carácter.

Creo que más o menos con estos ejemplos se entiende cual es el funcionamiento de este patrón de resolución de problemas que puede ser bastante útil si queremos sacar y comparar información entre elementos dentro de un mismo array.

Y hasta aquí este post nos vemos en el siguienteeeee, un abrazooooor