C++で合計がK未満となる部分配列の個数を求める方法

この記事では、C++を使用して「合計がK未満となる部分配列（サブ配列）の個数」を求める方法を解説します。問題設定としては、配列 arr[] と整数 K が与えられ、その中から要素の合計が K より小さくなる部分配列をすべて見つけ出します。以下に具体例を示します。

入力 : arr[] = {1, 11, 2, 3, 15}
K = 10
出力 : 4
該当する部分配列 : {1}, {2}, {3}, {2, 3}

解決のためのアプローチ

ここでは、この問題を解くための2つの異なる手法を紹介します。

方法1：総当たり法（Brute Force）

このアプローチでは、考えられるすべての部分配列を列挙してそれぞれの合計を計算し、その合計が K 未満であれば答えをカウントアップしていきます。

実装例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = {1, 11, 2, 3, 15}; // 与えられた配列
    int k = 10; // 与えられたK
    int size = sizeof(arr) / sizeof(int); // 配列のサイズ
    int ans = 0; // カウンタ変数
    for(int i = 0; i < size; i++){ // 外側のループ
        int sum = 0;
        for(int j = i; j < size; j++){ // 内側のループ
            sum = sum + arr[j];
            if(sum < k) // Kとの比較
                ans++; // 合計がK未満なら答えをインクリメント
        }
    }
    cout << ans << "\n";
    return 0;
}

出力

4

しかしこの方法は、時間計算量が O(N²)（Nは配列のサイズ）と非常に高く、効率的とは言えません。

そこで、プログラムの時間計算量を削減できる「スライディングウィンドウ法」を使った別の解法を見ていきましょう。

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

総当たり法とは異なり、この手法ではすべての部分配列を個別に調べる必要はありません。右端（end）を進めながら部分配列の合計を更新し、合計が K 以上になった時点で左端（start）を右端に追いつくまで動かす、という操作を配列全体の走査が完了するまで繰り返します。

実装例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = {1, 11, 2, 3, 15}; // 与えられた配列
    int k = 10; // 与えられたK
    int size = sizeof(arr) / sizeof(int); // 配列のサイズ
    int ans = 0; // カウンタ変数
    int start = 0; // 左端
    int end = 0; // 右端
    int sum = 0;
    while(end < size && start < size){ // 配列全体を走査し終えるまで
        while(sum >= k && start < end){
            sum = sum - arr[start];
            start++;
        }
        if(end >= start)
            ans = ans + end - start;
        sum += arr[end];
        end++;
    }
    cout << ans << "\n";
    return 0;
}

出力

4

このアプローチではスライディングウィンドウ技法を活用することで、大きな入力サイズに対しても高速に動作する、時間効率の良いプログラムを実現しています。

コードの解説

この手法では、まず合計が K 未満である間は通常どおり走査を進め、それに応じて答えを加算していきます。ここで重要なのは、合計が K 以上になったときの処理です。この状況では、合計が K を下回るまで、あるいは左端が右端に追いつくまで左端をインクリメントしていきます。さらに処理を進めると、新たに形成可能な他の部分配列も走査され、その合計が K 未満であれば順次答えに加算されるため、結果として正しい個数が得られます。

このアプローチは、先ほどの総当たり法と比較して非常に効率的であり、時間計算量は O(N)（Nは配列のサイズ）で済みます。

まとめ

この記事では、スライディングウィンドウ技法を用いて「合計が K 未満となる部分配列の個数」を求める問題を解きました。あわせて、この問題に対するC++プログラムと、単純な解法および効率的な解法という2つのアプローチについても学びました。なお、同じプログラムはC言語、Java、Pythonなど他の言語でも記述することが可能です。この記事が皆さんのお役に立てば幸いです。