算法精講：滑動窗口求和為S的連續正整數序列 (C語言實現)

滑動窗口算法：尋找和為S的連續正整數序列

問題描述

輸入正整數S，打印所有和為S的連續正整數序列（至少包含兩個數）。

核心思路：雙指針滑動窗口

• 初始化small = 1、big = 2，當前和curSum = 3。
• middle = (1 + S) / 2：因為序列至少兩個數，小數不超過S/2，大數不超過S/2 + 1，窗口右邊界無需超過middle。
• curSum == S：輸出序列，big++擴大窗口繼續搜尋。
• curSum > S：curSum -= small; small++縮小窗口左邊界。
• curSum < S：big++; curSum += big擴大窗口右邊界。

時間複雜度O(S)，空間複雜度O(1)。

C語言完整實現

#include <stdio.h>

void PrintContinuousSequence(int small, int big) {
    for (int i = small; i <= big; ++i) printf("%d ", i);
    printf("\n");
}

void FindContinuousSequence(int sum) {
    if (sum < 3) return;
    int small = 1, big = 2;
    int middle = (1 + sum) / 2;
    int curSum = small + big;
    while (small < middle) {
        if (curSum == sum) PrintContinuousSequence(small, big);
        while (curSum > sum && small < middle) {
            curSum -= small;
            ++small;
            if (curSum == sum) PrintContinuousSequence(small, big);
        }
        ++big;
        curSum += big;
    }
}

int main(void) {
    FindContinuousSequence(15);
    return 0;
}

運行輸出 (S=15)

1 2 3 4 5
4 5 6
7 8

三個序列均滿足連續正整數且和為15。

💡 遞歸與迭代對比

本題雖可用遞歸，但滑動窗口迭代法無棧溢出風險，且常數空間，更適合工程實際。