《剑指offer》第五十七题（为s的连续正数序列）

// 面试题57（二）：为s的连续正数序列
// 题目：输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。
// 例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1～5、
// 4～6和7～8。

#include <iostream>

void PrintContinuousSequence(int small, int big);

void FindContinuousSequence(int sum)
{
    if (sum < 3)
        return;

    int small = 1;
    int big = 2;
    int middle = (1 + sum) / 2;//因为序列要求至少包含两个数字，所以最大不会超过(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++;//然后就会出现小于要求值的情况，就加上++big
        curSum += big;
    }
}

void PrintContinuousSequence(int small, int big)//打印序列
{
    for (int i = small; i <= big; ++i)
        printf("%d ", i);

    printf("
");
}

// ====================测试代码====================
void Test(const char* testName, int sum)
{
    if (testName != nullptr)
        printf("%s for %d begins: 
", testName, sum);

    FindContinuousSequence(sum);
}

int main(int argc, char* argv[])
{
    Test("test1", 1);
    Test("test2", 3);
    Test("test3", 4);
    Test("test4", 9);
    Test("test5", 15);
    Test("test6", 100);
    system("pause");
    return 0;
}