C ++を使用して、合計がK未満のサブ配列の数を見つけます

この記事では、C++を使用して合計がK未満のサブ配列の数を調べます。この問題では、配列arr []と整数Kがあります。したがって、合計がK未満のサブ配列を見つける必要があります。例-

Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3}

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

次に、2つの異なる方法を使用して、特定の問題を解決します-

ブルートフォース

このアプローチでは、すべてのサブアレイを反復処理してそれらの合計を計算し、合計がk未満の場合はkと比較して、回答をインクリメントします。

例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = {1, 11, 2, 3, 15}; // given array
    int k = 10; // given k
    int size = sizeof(arr) / sizeof(int); // size of our array.
    int ans = 0; // counter variable.
    for(int i = 0; i < size; i++){ // outer loop.
        int sum = 0;
        for(int j = i; j < size; j++){ // inner loop.
            sum = sum + arr[j];
            if(sum < k) // comparing with k.
               ans++; // incrementing our ans if sum is less than k.
        }
    }
    cout << ans << "\n";
    return 0;
}

出力

4

ただし、このアプローチは、時間計算量が非常に高いため、あまり適切ではありません。 O（N * N） 、ここで、nは配列のサイズです。

スライディングウィンドウ方式を使用した代替ソリューションを検討します（これにより、プログラムの時間計算量を減らすことができます）。

効率的なアプローチ

ブルートフォースとは異なり 、すべてのサブアレイを通過するわけではありません。代わりに、サブ配列の合計がkを超えた場合にのみトラバースし、左の境界を右の境界まで移動し、配列全体がトラバースされるまで繰り返し続けます。

例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = {1, 11, 2, 3, 15}; // given array
    int k = 10; // given k
    int size = sizeof(arr) / sizeof(int); // size of our array.
    int ans = 0; // counter variable.
    int start = 0; // left border.
    int end = 0; // right border.
    int sum = 0;
    while(end < size && start < size){ // till the whole array is traversed.
        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 ++プログラムと、この問題を解決するための完全なアプローチ（通常および効率的）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。