C++で指定範囲内の合計を持つ部分配列の個数を効率的に求める方法

この記事では、C++を使って「合計が指定された範囲 [L, R] 内に収まる部分配列（サブ配列）の個数」を求める問題を解説します。正の整数からなる配列 arr[] と範囲 {L, R} が与えられ、その合計が L 以上 R 以下となる部分配列の総数を計算するのが目標です。

まず、問題の具体例を見てみましょう。

入力 : arr[] = {1, 4, 6}, L = 3, R = 8

出力 : 3

該当する部分配列は {1, 4}, {4}, {6} の3つです。

入力 : arr[] = {2, 3, 5, 8}, L = 4, R = 13

出力 : 6

該当する部分配列は {2, 3}, {2, 3, 5}, {3, 5},
{5}, {5, 8}, {8} の6つです。

解法のアプローチ

この問題を解くための方法として、主に2つのアプローチがあります。それぞれ順番に見ていきましょう。

1. 全探索（ブルートフォース）によるアプローチ

最も基本的な方法は、すべての部分配列の合計を実際に計算し、その合計が指定範囲内にあるかどうかを一つずつ確認するものです。しかし、この方法では配列のサイズを n としたとき、時間計算量が O(n²) となり、配列が大きくなると処理に非常に時間がかかってしまいます。

2. 効率的なアプローチ（スライディングウィンドウ法）

計算時間を大幅に短縮するために、「スライディングウィンドウ（尺取り法）」と呼ばれるテクニックを使用します。この手法を用いることで、O(n) の線形時間で結果を高速に求めることができます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int subCount(int *arr, int n, int x){
    int start = 0, end = 0, sum = 0, count = 0;
    while (end < n){ // 右端を動かすループ
        sum = sum + arr[end];
        while(start <= end && sum >= x){ // 左端を動かすループ
            sum = sum - arr[start]; // 左端を進めながら合計から要素を除外
            start++;                // 左端を移動
        }
        count = count + ((end - start) + 1); // 部分配列の個数をカウント
        end++;
    }
    return count;
}
int main(){
    int arr[] = { 1, 4, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int L = 3;
    int R = 8;
    int answer;
    answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // 最終的な答え
    cout << answer << "\n";
    return 0;
}

実行結果

3

コードの解説

このアプローチのポイントは、「合計が範囲の上限 R 以下である部分配列の個数」から「合計が下限 L 未満である部分配列の個数」を差し引くことで、目的の個数を導き出している点です。

subCount 関数の仕組み

subCount 関数はスライディングウィンドウのテクニックを使い、「合計が x 未満となる部分配列の個数」を求めます。

まず、start と end をどちらも 0 で初期化し、配列を走査しながら start から end までの要素の合計を管理します。合計が x 以上になった場合には、start を進めながら合計から要素を取り除いていきます。これにより、合計が x 未満になるか、start が end を追い越すまで左端を縮めていきます。

その後、現在のウィンドウ内に含まれる部分配列の個数（end - start + 1）を count に加算し、右端 end を1つ進めます。外側のループが終了した時点で、条件を満たす部分配列の総数を返します。

なお、この方法が機能するのは配列の要素がすべて正の整数であるためです。右端を伸ばせば合計は必ず増加し、左端を縮めれば必ず減少するため、ウィンドウを単調に操作できます。

まとめ

この記事では、スライディングウィンドウのテクニックを活用することで、指定範囲内の合計を持つ部分配列の個数を O(n) の時間計算量で効率的に求める方法を解説しました。全探索のような非効率な方法ではなく、このような効率的なアルゴリズムを身につけることで、大規模なデータにも対応できるようになります。同じロジックは C、Java、Python など他のプログラミング言語でも同様に実装可能です。