ツーポインタトリックJavaScriptプログラム

JavaScript プログラムのダブル ポインター テクノロジは、線形時間計算量を必要とするさまざまな問題を解決するためによく使用されるアルゴリズム手法です。この手法は、配列、文​​字列、またはリンク リストを検索、並べ替え、または操作する問題の解決に広く使用されています。この方法は、2 つのポインターを維持し、1 つはデータ構造の先頭から開始し、もう 1 つはデータ構造の末尾から開始し、解が見つかるまで逆方向に反復処理することによって機能します。

このチュートリアルでは、ダブル ポインター テクノロジの概念と、JavaScript プログラミング言語を使用してそれを実装する方法について説明します。それでは、まず問題文から始めて、それからこの楽しいチュートリアルを進めてみましょう。

＃＃＃問題文＃＃＃

N 個の整数を含む昇順にソートされた配列 A がある場合、その合計が X に等しくなるような要素のペア (A[i]、A[j]) があるかどうかを確認します。

次に、いくつかの例を通して上記のプログラムの役割を理解しましょう。

リーリー

説明

-この場合、入力配列の要素ペア(3, 9)が追加されて目標合計が12になり、プログラムはインデックス1と4の要素ペアを正しく識別します。 リーリー

説明

-この場合、ターゲット合計が9の場合、そのようなペアは存在せず、関数は「ペアが見つかりません」を返す必要があります。 ＃＃＃アルゴリズム＃＃＃ ダブル ポインター トリックを使用して、ソートされた配列内に合計が指定されたターゲット値に等しい要素のペアがあるかどうかを検出するアルゴリズム -

2 つのポインターを左 = 0、右 = 配列の長さ - 1 で初期化します。

• 左辺が右辺より小さい場合は、次の操作を実行します

• インデックスの左右の要素の合計を計算します。

  • 合計がターゲット値と等しい場合は、左のインデックスと右のインデックスを返します。

  • 合計が目標値より小さい場合は、左を増やします。

  • 合計が目標値より大きい場合は、右側を減らします。

  そのようなペアが存在しない場合は、null を返します。

• 上記のアルゴリズムは、ダブル ポインター テクノロジを使用して、並べ替えられた配列内の要素のペアを検索し、それらの合計が指定されたターゲット値と等しくなるようにします。ポインタは配列のどちらかの端から始まり、ポインタの要素の合計がターゲット値とどのように比較されるかに基づいて、互いに向かって移動します。合計が目標値より小さい場合は、左ポインタを右に移動して合計を増やします。合計が目標値より大きい場合は、右ポインタを左に移動して合計を減らします。合計がターゲット値と等しい場合、プログラムは要素のペアのインデックスを返します。そのような要素のペアが存在しない場合、プログラムは「ペアが見つかりません」を返します。

次に、例を通してこのアルゴリズムを理解しましょう。この例では、JavaScript を使用して前に説明した問題ステートメントを実装します。

Example

の中国語訳は次のとおりです:

Example

このプログラムでは、2 ポインター手法を使用して、指定された並べ替えられた配列内に、合計が指定されたターゲットに等しい要素のペアが存在するかどうかを確認しました。配列を反復処理し、要素の合計に基づいてポインターを移動することによって、ポインターで、プログラムは要素のペア (存在する場合) を O(N) 時間の計算量で効率的に見つけます。ここで、N は配列内の要素の数です。

リーリー ＃＃＃結論は＃＃＃

このチュートリアルでは、ダブル ポインター手法の概念と、JavaScript プログラミング言語を使用してそれを実装し、並べ替えられた配列内の要素のペアの検索または比較に関する問題を解決する方法について説明しました。また、2 ポインター手法を使用して、要素の合計が指定されたターゲットに等しくなるような要素のペアを見つけるアルゴリズムも学習しました。この手法を使用すると、時間の複雑さの点でプログラムの効率を大幅に向上させることができます。具体的には、ダブルポインタ テクノロジは、この種の問題を O(N) の時間計算量で解決できます。これは、O(N^2) のブルート フォース手法よりもはるかに高速です。したがって、同様の問題を効率的に解決するには、このテクニックを学び、適用することが非常に重要です。

以上がツーポインタトリックJavaScriptプログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。