CKTIS / C
Ventana deslizante para valores no negativos
Una ventana deslizante mantiene un tramo contiguo de un arreglo y desplaza sus límites sin volver a sumar todos los elementos cada vez. La variante que reduce la ventana requiere valores de entrada no negativos.
Versión: C23; repository compiler flag, production runtime not attested
Sintaxis
Use this shrinking-window rule only when all input values are nonnegative and the target is strictly positive. Use a running-sum type that can represent every intermediate sum without overflow, including the sum immediately after adding an element and before shrinking the window. Maintain left and right window boundaries and add each entering value to the running sum. While the current sum is at least the target, compare the current window length with the shortest found so far and update it if needed. Then subtract the leftmost value and advance the left boundary, even if that removal drops the sum below the target. An empty window has sum zero, so the positive target ensures that the loop stops before attempting to remove another element.Una ventana deslizante tiene un límite izquierdo y otro derecho. Al avanzar el límite derecho, el siguiente valor se añade a la suma acumulada. Cuando la suma alcanza el umbral, el límite izquierdo avanza mientras se siga cumpliendo la condición, y se restan los valores que salen. Cada elemento entra en la ventana como máximo una vez y sale de ella como máximo una vez, por lo que el recorrido tarda un tiempo lineal.
Es esencial que los valores de entrada no sean negativos. Añadir un número no negativo no puede reducir la suma, y quitarlo por la izquierda no puede aumentarla. Este comportamiento monótono permite reducir la ventana con seguridad. Con valores negativos, este razonamiento deja de funcionar y hace falta otro algoritmo.
El ejemplo busca el tramo contiguo más corto cuya suma sea al menos 7. Para 2, 1, 5, 2, 3, 2, el programa imprime 2 porque el tramo 5, 2 cumple la condición.
Ejemplos
#include <stddef.h>
#include <stdio.h>
int main(void) {
const int values[] = {2, 1, 5, 2, 3, 2};
const size_t count = sizeof values / sizeof values[0];
const int target = 7;
size_t left = 0;
size_t best = count + 1;
int sum = 0;
for (size_t right = 0; right < count; ++right) {
sum += values[right];
while (sum >= target) {
const size_t length = right - left + 1;
if (length < best) best = length;
sum -= values[left++];
}
}
if (best == count + 1) printf("none\n");
else printf("%zu\n", best);
return 0;
}Resultado
2
El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.