Patrones de ventana deslizante y de dos punteros

Patrón 1: Ventana constante (como ventana = 4 o algún valor entero)

Por ejemplo, dada una matriz de números enteros (-ve y ve), encuentre la suma máxima para la ventana contigua de tamaño k.

Patrón 2:(Tamaño de ventana variable) Subarreglo/subcadena más grande con ejemplo: suma

• Aproches:
  • Fuerza bruta: Genere todos los subarreglos posibles y elija el subarreglo de longitud máxima con suma
• Mejor/óptimo: Utilice dos punteros y una ventana deslizante para reducir la complejidad del tiempo a O(n)

Patrón 3: No de subconjunto/subcadena donde como suma=k.
Esto es muy difícil de resolver porque resulta difícil cuándo expandirse (derecha) o cuándo reducirse (izquierda).

Este problema se puede resolver usando el Patrón 2
Para resolver problemas como encontrar el número de subcadenas donde suma =k.

• Esto se puede dividir en

  • Buscar subarreglos donde suma
  • Encontrar subarreglo donde suma

Patrón 4: Encuentra la ventana más corta/mínima

Diferentes enfoques para el patrón 2:
Ejemplo: Subarreglo más grande con suma

public class Sample{
    public static void main(String args[]){
        n = 10;
        int arr[] = new int[n];

        //Brute force approach for finding the longest subarray with sum  k) break; /// optimization if the sum is greater than the k, what is the point in going forward? 
            }
        }

Mejor enfoque usando los dos punteros y la ventana deslizante

        //O(n n) in the worst case r will move from 0 to n and in the worst case left will move from 0 0 n as well so 2n
        int left = 0;
        int right =0;
        int sum = 0;
        int maxLen = 0;
        while(right k){
                sum = sum-arr[left];
                left  ;
            }
            if(sum 



Enfoque óptimo: 

Sabemos que si encontramos el subarreglo almacenamos su longitud en maxLen, pero mientras agregamos arr[right] si la suma es mayor que k entonces actualmente estamos reduciendo hacia la izquierda haciendo sum = sum-arr[left] y haciendo left . 

Sabemos que la longitud máxima actual es maxLen, si seguimos reduciendo el índice izquierdo podríamos obtener otro subarreglo que satisfaga la condición ( maxLen, entonces solo se actualizará maxLen.

Un enfoque óptimo será reducir solo la izquierda siempre que la longitud del subarreglo sea mayor que maxLen cuando el subarreglo no cumpla la condición (


        int right =0;
        int sum = 0;
        int maxLen = 0;
        while(right k){// this will ensure that the left is incremented one by one (not till the sum