【C++】合計がNになる連続する整数列をすべて出力するアルゴリズム

問題概要

この問題では、正の整数 N が与えられ、合計がちょうど N と等しくなる連続する整数列をすべて見つけて出力します。

まず、具体例で問題を確認してみましょう。

入力：N = 15

出力：
1 2 3 4 5
7 8

上記の出力では、「1+2+3+4+5 = 15」と「7+8 = 15」の2つの連続数列が条件を満たしています。

解法1：単純な全探索（ブルートフォース）

最もシンプルなアプローチは、開始位置を 1 から N/2 まで順にずらしながら、連続する数を足し合わせていき、合計が N に一致した時点でその数列を出力する方法です。

ここで探索範囲を N/2 までに限定できるのは、2つ以上の連続する正の整数の合計は必ず「開始値 × 2」より大きくなるためです。つまり、開始値が N/2 を超えると合計が N を超えてしまいます。

サンプルコード

#include <iostream>
using namespace std;

void printConsecutiveSum(int N){
    int start = 1, end = (N+1)/2;
    while (start < end){
        int sum = 0;
        for (int i = start; i <= end; i++){
            sum = sum + i;
            if (sum == N){
                for (int j = start; j <= i; j++)
                    cout << j << " ";
                cout << endl;
                break;
            }
            if (sum > N)
                break;
        }
        sum = 0;
        start++;
    }
}

int main(){
    int N = 25;
    cout << "合計が " << N << " になる連続する数列は次の通りです:\n";
    printConsecutiveSum(N);
    return 0;
}

実行結果

合計が 25 になる連続する数列は次の通りです:
3 4 5 6 7
12 13

この方法は実装が簡単で分かりやすい反面、開始位置ごとに毎回最初から足し算をやり直すため、時間計算量は O(N²) となり、大きな N に対しては非効率です。

解法2：スライディングウィンドウによる最適化

より効率的なのがスライディングウィンドウ（尺取り法）を使った解法です。現在の区間の合計を保持したまま、次のようにウィンドウを伸縮させます。

• 合計が N より小さい場合： 終端 end を1つ進めて合計に加える（ウィンドウを拡大）
• 合計が N より大きい場合： 先頭 start の値を合計から引いて start を1つ進める（ウィンドウを縮小）
• 合計が N と一致した場合： その区間の数列を出力し、先頭を1つ進めて次の候補を探す

この手法では各要素が最大でも加算・減算それぞれ1回しか処理されないため、時間計算量は O(N) に抑えられます。

サンプルコード

#include <iostream>
using namespace std;

void printConsecutiveSum(int N){
    int start = 1, end = 1;
    int sum = 1; // 現在のウィンドウ [start, end] の合計
    while (start <= N/2){
        if (sum < N){
            // 合計が足りないのでウィンドウを拡大
            end += 1;
            sum += end;
        }
        else if (sum > N){
            // 合計が超過したので先頭を除外して縮小
            sum -= start;
            start += 1;
        }
        else { // sum == N
            // 条件を満たす数列を出力
            for (int i = start; i <= end; ++i)
                cout << i << " ";
            cout << endl;
            sum -= start;
            start += 1;
        }
    }
}

int main(){
    int N = 25;
    cout << "合計が " << N << " になる連続する数列は次の通りです:\n";
    printConsecutiveSum(N);
    return 0;
}

実行結果

合計が 25 になる連続する数列は次の通りです:
3 4 5 6 7
12 13

まとめ

連続する整数の合計を扱う問題では、一度計算した部分和を捨てずに再利用するスライディングウィンドウが有効です。同様のテクニックは「部分配列の合計が目標値に一致する区間を探す」問題などにも応用できます。