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

上記のコードの説明

このメソッドでは、合計が上限よりも小さい部分配列の数を数えます。指定された範囲の制限を計算し、合計が指定された範囲の上限よりも小さい部分配列の数を減算します。指定された範囲の下限未満を取得するには、subcount 関数を使用します。

サブカウント関数

この関数は、スライディング ウィンドウ手法を使用して、カウントが x 未満のサブ配列のカウントを見つけます。

まず、「end」から開始し、 "start"、それらの値はすべて 0 です。配列を反復処理するときは、最初から最後まで要素の合計を維持します。その後、start が end と等しく、合計が x 以上の場合、start を移動し始め、合計から要素を取り除きながら合計を減らし続けます。

合計が x より小さくなるか、開始値が終了値より大きくなるまで。次に、サブ配列数だけカウントを増やし、右境界を 1 ずつ増やします。ここで、外側のループが終了した後、部分配列の合計数を返します。

結論

この論文では、スライディング ウィンドウ手法を使用して、O(n) 時間計算量で合計が所定の範囲内にある部分配列の数を見つける問題を解決しました。また、この問題については C プログラムから学び、それを簡単に (通常かつ効率的に) 解決できる完全な方法についても学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。

以上がC++ を使用して、指定された範囲内の合計を持つ部分配列の数を見つけるプログラムを作成します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。