C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

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 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)); // Final Answer.
    cout << answer << "\n";
    return 0;
}

出力

3

上記のコードの説明

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

サブカウント関数

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

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

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

結論

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


  1. C++を使用して停止ステーションの数を見つける

    ポイントXとYの間にn個の中間駅があります。2つの駅が隣接しないように、s駅に停車するように列車を配置できるさまざまな方法の数を数えます。そのため、この記事では、停車駅の数を見つけるためのあらゆる可能なアプローチについて説明します。問題を見ると、sの駅数で列車を止めることができる組み合わせを見つける必要があることがわかります。 問題を解決するためのアプローチ 中間駅が8つあり、3つの中間駅で電車を止める方法を見つける必要がある例を見てみましょう。 n = 8, s = 3 (n-s)、つまり電車が止まらない駅が5つ残っています 電車が止まらないA、B、C、D、Eの5つの駅があります

  2. C ++を使用して、指定されたポイントから可能な四辺形の数を見つけます

    四辺形は、ユークリッド平面幾何学で4つの頂点と4つのエッジを持つポリゴンを形成します。名前4-gonなど。四辺形の他の名前に含まれ、正方形、表示スタイルなどとしても知られています。 この記事では、与えられた点から可能な四辺形の数を見つけるためのアプローチを説明します。この問題では、デカルト平面に提供された4つの点(x、y)を使用して作成できる四辺形の数を調べる必要があります。だからここに与えられた問題の例があります- Input : A( -2, 8 ), B( -2, 0 ), C( 6, -1 ), D( 0, 8 ) Output : 1 Explanation : One quadr