CKTIS / C
Janela deslizante para valores não negativos
Uma janela deslizante mantém um segmento contíguo de um vetor e desloca os seus limites sem voltar a somar todos os elementos de cada vez. A variante que reduz a janela exige valores de entrada não negativos.
Versão: C23; repository compiler flag, production runtime not attested
Sintaxe
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.Uma janela deslizante tem um limite esquerdo e um limite direito. Quando o limite direito avança, o valor seguinte é adicionado à soma acumulada. Assim que a soma atinge o limiar, o limite esquerdo avança enquanto a condição se mantiver satisfeita, e os valores retirados são subtraídos. Cada elemento entra na janela no máximo uma vez e sai dela no máximo uma vez, pelo que o percurso demora tempo linear.
É essencial que os valores de entrada não sejam negativos. Adicionar um número não negativo não pode reduzir a soma, e retirá-lo pela esquerda não pode aumentá-la. Este comportamento monótono permite reduzir a janela em segurança. Com valores negativos, este raciocínio deixa de funcionar e é necessário outro algoritmo.
O exemplo procura o segmento contíguo mais curto cuja soma seja pelo menos 7. Para 2, 1, 5, 2, 3, 2, o programa escreve 2 porque o segmento 5, 2 satisfaz a condição.
Exemplos
#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
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.