1. 概要

このチュートリアルでは、与えられた合計でサブ配列の数を見つける問題について説明します。

まず、問題を定義し、それを説明するための例を示します。 次に、それを解決するための2つの異なるアプローチを提示し、それらの実装と時間計算量を処理します。

2. 問題の定義

配列があり、合計が。に等しいサブ配列の数を数えるように求められたとします。

配列のサブ配列は、配列要素の連続した範囲であることを思い出してください。

次の例を見てみましょう。

配列と目的の合計が与えられた場合（赤いセルは合計がに等しいサブ配列を定義します）：

ご覧のとおり、合計が。に等しいサブ配列があるため、ここでの答えは4つです。

3. 素朴なアプローチ

3.1. 本旨

このアプローチの主なアイデアは、可能なサブアレイの合計がに等しいかどうかをチェックすることです。

最初に、サブアレイのすべての可能な開始を実行します。 次に、開始ごとに修正し、可能なすべての終了を試します。 次に、有効な終了を探している間に、現在の数値をそのサブ配列の合計に追加します。 現在のサブアレイの合計がいつか等しい場合、答えを1つ増やします。 それ以外の場合は、そのサブ配列を無視します。

最後に、答えは、合計がに等しいサブ配列の数に等しくなります。

3.2. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初に、合計が。に等しいサブ配列の数を返す関数を宣言します。 この関数には、指定された配列を表す2つのパラメーターと、目的の合計があります。

最初に、有効なサブ配列の数を格納するを宣言します。 次に、指定された配列の各位置から新しいサブ配列を開始しようとします。 また、を宣言します。これは、で始まるサブ配列の合計を格納します。

次に、可能なすべてのサブアレイの終了を繰り返し処理します。 終了ポインタを移動しながら、現在のサブ配列の最後に要素を追加します。 その後、がに等しいかどうかをチェックすることにより、現在のサブアレイが有効かどうかをチェックします。 もしそうなら、私たちは1つ増やします。 それ以外の場合、現在のサブアレイは無効です。

最後に、は、合計がに等しいサブ配列の数に等しくなります。

3.3. 複雑さ

このアルゴリズムの時間計算量はです。ここで、は指定された配列の長さです。 この複雑さは、指定された配列の各位置のサブ配列の開始として固定し、そのサブ配列の終了となる可能性のある全体的な位置を繰り返したためです。

4. プレフィックスサムアプローチ

4.1. 本旨

このアプローチの主なアイデアは、プレフィックス合計手法を利用することです（Recallは、配列の先頭からインデックスまでのすべての要素の合計を格納します）。

最初に、指定された配列のプレフィックス合計を計算します。 次に、指定された配列位置ごとに、それをサブ配列の終わりとして修正し、サブ配列を有効にする可能性のあるサブ配列の開始数を取得しようとします。 次の式で、固定位置で有効なサブ配列の終了を与える有効な開始を表すことができます。

   

したがって、現在の位置で終了する可能性のある有効なサブアレイの開始数は、の前にある位置のプレフィックス合計値の数と等しくなります。 次に、ポインタを移動しながら、その位置のプレフィックス合計値を増やします。

最後に、は、合計が。に等しいサブ配列の数を表します。

4.2. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初は、前のアプローチと同じ機能があります。

まず、配列を宣言します。これにより、指定された配列の先頭から特定の位置までのすべての要素の合計が格納されます。 式を適用して、指定された配列のを計算します。

次に、有効なサブ配列の数を格納するを宣言します。 さらに、特定の値の出現回数を格納するハッシュマップを宣言します。

第3に、各位置を反復処理し、サブアレイの終わりとして修正します。可能なすべてのサブアレイの開始数を取得する必要があります。 位置で終了するサブ配列は、の場合に限り、有効な開始を持ちます。 したがって、に等しい位置の数にを追加します。 その後、を1つずつ増やしていきます。

最後に、は、合計がに等しいサブ配列の数に等しくなります。

4.3. 複雑

このアルゴリズムの時間計算量はです。ここで、は指定された配列の長さです。 この複雑さは、各要素を1回だけ繰り返すためです。

注：以前の時間計算量は、ハッシュマップ操作の複雑さを表す定数係数で乗算できます。

5. 結論

この記事では、与えられた合計でサブ配列の数を見つける問題について説明しました。 問題を説明するための例を提供し、問題を解決するための2つの異なるアプローチを検討しました。ここで、2番目のアプローチの方が時間計算量が優れていました。

最後に、それらの実装をウォークスルーし、それぞれの背後にある考え方を説明しました。