CKTIS / C
Плъзгащ се прозорец за неотрицателни стойности
Плъзгащият се прозорец обхваща непрекъснат участък от масив и мести границите му, без всеки път да сумира всички елементи отново. Вариантът със свиване на прозореца изисква неотрицателни входни стойности.
Версия: C23; repository compiler flag, production runtime not attested
Синтаксис
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.Плъзгащият се прозорец има лява и дясна граница. При преместване на дясната граница следващата стойност се добавя към текущата сума. Щом сумата достигне прага, лявата граница се мести надясно, докато условието остава изпълнено, а премахнатите стойности се изваждат от сумата. Всеки елемент влиза в прозореца най-много веднъж и го напуска най-много веднъж, затова обхождането отнема линейно време.
Изискването входните стойности да са неотрицателни е съществено. Добавянето на неотрицателно число не може да намали сумата, а премахването му отляво не може да я увеличи. Тази монотонност позволява прозорецът да се свива безопасно. При отрицателни стойности това разсъждение вече не е валидно и е нужен друг алгоритъм.
Примерът търси най-късия непрекъснат участък със сума поне 7. За 2, 1, 5, 2, 3, 2 програмата извежда 2, защото участъкът 5, 2 изпълнява условието.
Примери
#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;
}Резултат
2
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.