CKTIS / C
Gleitendes Fenster für nichtnegative Werte
Ein gleitendes Fenster umfasst einen zusammenhängenden Bereich eines Arrays und verschiebt dessen Grenzen, ohne die Summe jedes Mal neu zu berechnen. Die Variante mit Verkleinerung des Fensters setzt nichtnegative Eingabewerte voraus.
Version: C23; repository compiler flag, production runtime not attested
Syntax
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.Ein gleitendes Fenster hat eine linke und eine rechte Grenze. An der rechten Grenze kommt der nächste Wert zur laufenden Summe hinzu. Sobald die Summe den Zielwert erreicht, wird die linke Grenze nach rechts verschoben, solange die Bedingung erfüllt bleibt. Die entfernten Werte werden abgezogen. Jedes Element wird höchstens einmal aufgenommen und höchstens einmal entfernt. Der Durchlauf benötigt daher lineare Zeit.
Die Voraussetzung, dass die Eingabewerte nichtnegativ sind, ist entscheidend. Wird eine nichtnegative Zahl hinzugefügt, kann die Summe nicht sinken. Wird sie links entfernt, kann die Summe nicht steigen. Dieses monotone Verhalten erlaubt es, das Fenster sicher zu verkleinern. Bei negativen Werten gilt diese Überlegung nicht mehr, und es ist ein anderer Algorithmus nötig.
Das Beispiel sucht den kürzesten zusammenhängenden Bereich mit einer Summe von mindestens 7. Für 2, 1, 5, 2, 3, 2 gibt das Programm 2 aus, weil der Bereich 5, 2 die Bedingung erfüllt.
Beispiele
#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;
}Ergebnis
2
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.