Ventana variable con dos punteros

Algunos problemas no fijan la longitud de la ventana. En su lugar, la ventana se expande y se contrae para mantener una condición verdadera, como que una suma permanezca por debajo de un límite.

Mantenga dos índices, left y right, que marquen los extremos de la ventana. El puntero right se expande mientras left queda atrás para reducirla cuando sea necesario.

Recorra hacia la derecha todos los elementos e inclúyalo en la ventana. Actualice el estado acumulado, por ejemplo, añadiendo el nuevo valor a una suma.

Mientras la ventana viole la regla, mueva left hacia la derecha y elimine ese elemento. Así restablece la condición sin retroceder.

Cuando termina el bucle interno, la ventana de left a right es válida. Su longitud es right menos left más uno, y ya puede utilizarla.

Actualice la respuesta con esta ventana válida, que a menudo será la más larga encontrada. Hágalo en cada iteración para no omitir ninguna.

Cada puntero solo avanza hacia delante, nunca retrocede. left y right avanzan juntos como máximo n pasos, por lo que todo el recorrido cuesta O(n).

Esto funciona cuando ampliar la ventana solo hace que la condición sea más difícil de satisfacer. Ese comportamiento monótono es lo que permite que left nunca retroceda.

Para encontrar la ventana válida más corta, redúzcala mientras la regla siga cumpliéndose y registre el resultado antes de detenerse. La mecánica de los punteros no cambia.

Si al reducir la ventana esta puede quedar vacía, compruebe que left supere a right. Confirme también que realmente se encontró una respuesta antes de devolverla.

Elija una ventana variable cuando el problema pida el tramo contiguo más largo o más corto que cumpla una condición sobre sus elementos.

Expanda right para incluir elementos, reduzca left mientras se incumpla la regla y registre cada ventana válida. Los punteros que solo avanzan mantienen el costo en O(n). ✅