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

本記事では、C++を用いて「合計が指定された範囲に収まる部分配列の個数」を求める問題を解説します。正の整数からなる配列 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つです。

解法のアプローチ

この問題をC++で解くための方法として、次の2つのアプローチを紹介します。

全探索（ブルートフォース）アプローチ

最も基本的な方法は、すべての部分配列の合計を順番に計算し、その値が指定範囲内にあるかどうかを確認するものです。しかし、この方法では時間計算量が O(n×n)（nは配列のサイズ）になるため、配列が大きくなると膨大な処理時間が必要となってしまいます。

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

処理時間を大幅に短縮するために、「スライディングウィンドウ」と呼ばれるテクニックを使った効率的なアプローチを採用します。この手法を利用すれば、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){ // このループでは右端（end）を移動させます
        sum = sum + arr[end];
        while(start <= end && sum >= x){ // このループで左端（start）を移動させます
            sum = sum - arr[start]; // 左端を動かす際、除外する要素の分だけ合計を減らします。
            start++;                // 左端を1つ進めます。
        }
        count = count + ((end - start) + 1); // 条件を満たす部分配列を数えます。
        end++;
    }
    return count;
}
int main(){
    int n; // 配列のサイズ
    int L, R;
    cin >> n;
    int arr[n];
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    cin >> L >> R;
    int answer;
    answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // 最終的な答え。
    cout << answer << "\n";
    return 0;
}

出力

1

コードの解説

このアプローチでは、まず subCount 関数を用いて「合計が指定範囲の上限 R 未満となる部分配列」の個数を数え、そこから「合計が下限未満（L−1 未満）となる部分配列」の個数を差し引くことで、目的の答えを導き出しています。

subCount関数の仕組み

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

最初に、start と end の両方を 0 で初期化します。配列を走査しながら、start から end までの要素の合計を常に管理します。もし start が end 以下であり、かつ合計が x 以上になった場合には、start を進めながら、窓から取り除く要素の分だけ sum を減らしていきます。

この操作は、sum が x より小さくなるか、start が end を超えるまで続けます。その後、現在の窓に含まれる部分配列の数だけ count を加算し、右端（end）を1つ進めます。外側のループがすべて終了した時点で、部分配列の総数を返します。

まとめ

本記事では、スライディングウィンドウのテクニックを活用することで、合計が指定範囲に収まる部分配列の個数を O(n) の時間計算量で求める方法を解説しました。単純な全探索と効率的な手法の両方を理解しておけば、状況に応じて最適な実装を選択できるようになります。なお、同じロジックはC言語、Java、Pythonなど他のプログラミング言語でも同様に実装可能です。