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 は配列のサイズです。

スライディング ウィンドウ アプローチを使用して代替ソリューションを探します (これは、プログラムの時間の複雑さを軽減するのに役立ちます)。

効率的な方法

ブルート フォース攻撃

効率的な方法

strong>とは異なり、すべてのサブ配列を走査するわけではありません。代わりに、部分配列の合計が 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 未満になるまで繰り返し、それに基づいて答えを増分します。これは、次の場合に発生するコードの重要な変更です。 sum k 以上の場合。この場合、左境界が k 以下になるか、合計が k 以上になるまで、左境界を増分し始めます。処理がさらに進むにつれて、形成される可能性のある他のサブアレイを反復処理します。 k 未満のこれらの新しい部分配列の合計が答えに追加されるため、答えは増加します。

前の ブルート フォース ソリューション と比較すると、この方法は時間計算量が O(N) (N は配列サイズの数) であるため、非常に効率的です。 。

結論

この記事では、スライディング ウィンドウ手法を使用して、合計が k 未満である部分配列の数を見つける問題を解決しました。また、この問題に対する C プログラムと、それを解決するための完全なアプローチ (簡単かつ効率的な) についても学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ で書かれており、合計が K 未満である部分配列の数を求めます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。