C++で特定の範囲に合計を持つサブ配列の数を見つける

この記事では、C ++プログラムを使用して、特定の範囲に合計を持つサブ配列の数を解決します。正の整数の配列arr[]と範囲{L、R}があり、LからRまでの指定された範囲の合計を持つサブ配列の総数を計算する必要があります。したがって、問題の簡単な例を次に示します。

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

Output : 3

The subarrays are {1, 4}, {4}, {6}.


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

Output : 6

The subarrays are {2, 3}, {2, 3, 5}, {3, 5},
{5}, {5, 8}, {8}.

解決策を見つけるためのアプローチ

C++の問題を使用してこの問題を解決する2つの方法を説明します-

ブルートフォースアプローチ

最も基本的なブルートフォースアプローチを使用して、すべてのサブアレイの合計を計算し、その合計が指定された範囲内に存在するかどうかを確認します。 （ただし、このアプローチでは、時間計算量がO（n * n）であり、nは配列のサイズであるため、多くの時間がかかります。）

効率的なアプローチ

時間を節約するために、効率的なアプローチと呼ばれる別の方法を使用します。現在、効率的なアプローチはスライディングウィンドウ手法を使用しており、この手法を使用して、O（n）で結果をはるかに高速または効率的に計算します。

例

#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){ // we will be moving right border in this loop
        sum = sum + arr[end];
        while(start <= end && sum >= x){ // this loop will move our left border
            sum = sum - arr[start]; // we will decrement sum while moving left border.
                                   // For excluding the previous elements.
            start++;                // and move the left border.
        }
        count = count + ((end - start) + 1); // counting the subarrays.
        end++;
    }
    return count;
}
int main(){
    int n; // size of array
    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)); // Final Answer.
    cout << answer << "\n";
    return 0;
}

出力

1

上記のコードの説明

このアプローチでは、合計が指定された範囲の上限よりも小さいサブアレイの数をカウントし、次に、サブカウント関数を使用して、合計が指定された範囲の下限よりも小さいサブアレイの数を減算します。

サブカウント関数

この関数は、スライディングウィンドウ手法を使用して、カウントがx未満のサブアレイのカウントを検索します。

最初は、値として0を使用して'endとstart'の両方から開始します。配列をトラバースするとき、最初から最後まで要素の合計を維持します。その後、開始が終了に等しく、合計がx以上の場合、開始を移動し始め、合計から要素を削除しながら合計を減らし続けます。

合計がx未満になるか、開始が終了より大きくなるまで。次に、サブアレイカウントでカウントをインクリメントし、次に右の境界線を1でインクリメントします。ここで、外側のループが終了した後、サブアレイの合計カウントを返します。

結論

この記事では、スライディングウィンドウ手法を使用して、O（n）時間計算量の特定の範囲に合計を持つサブアレイの数を見つける問題を解決します。また、この問題のC ++プログラムと、この問題を簡単に解決できる完全なアプローチ（通常および効率的）からも学びました。同じプログラムをC、java、pythonなどの他の言語で書くことができます。