每日一道算法題：輸出和為n的連續正整數序列

題目：輸入一個正數n，輸出所有和為n連續正數序列。

例如輸入15，由于1+2+3+4+5=4+5+6=7+8=15，是以輸出3個連續序列1-5、4-6和7-8。

解題思路：我們以正數21為例，由于21=1+2+3+4+5+6=6+7+8=10+11，那麼題目要求輸出的連續序列為1-6、6-8和10-11。假設計算出的某個序列為m-n，那麼這個序列中正數的個數為（n-m+1），這裡，可以參照高斯求解1+2+3+...+100的思路，所要解的式子為21=（n+m）*（n-m+1）/2。通過從數字1開始周遊，到哪個數停止呢？題目所要求的是連續正整數之和，可以知道正數n至少為兩個數之和，并且這兩個數必須是連續的，那麼，從數字1開始周遊一直到正數n的一半取上限值即可。代碼如下：

#include <iostream>
using namespace std;

#define N 21

int main(){
    int start = 0;
    int end = 0;
    for (start = 1; start <= N/2+1; start++){
        for (end = start+1; end <= N/2+1; end++){
            if ((start+end) * (end-start+1) == 2 * N){
                cout << "結果為: " << start << "-" << end << endl;
                break;
            }
        }
    }
    system("pause");
    return 0;
}
           

上面代碼的時間複雜度為O(n*n)，一般情況下是不會采用上述思路的，那麼下面這種類似于遊标卡尺的思路在時間複雜度方面表現的更好一些。還是假設計算出的某個序列為m-n，另m=1，n=2，m到n之間的和sum=1，如果m到n之間的和sum等于正數n，輸出這個序列；如果和sum小于n，另n繼續向右移動，加上更大的數，直到和sum等于n為止；如果和sum大于n，另m向右移動，減去更小的數，直到和sum等于n為止。代碼如下：

#include <iostream>
using namespace std;

void func(int N){
    if (N<=0){
        return;
    }
    int start = 1;
    int end = 2;
    int count = (N+1)/2;
    int sum = 1;
    while (start <= count){
        if (sum == N){
            cout << "結果為: " << start << "-" << (end-1) << endl;
            sum -= start;
            start++;
        }
        else if (sum < N){
            sum += end;
            end++;
        }
        else{
            sum -= start;
            start++;
        }
    }
}

int main(){
    func(21);
    system("pause");
    return 0;
}