最新のソフトウェア エンジニアリングにおける問題解決に関するブログ シリーズへようこそ!

パート 1 では、要素の頻度を効率的にカウントすることでアルゴリズムを最適化するための強力な手法である 周波数カウンター パターンを検討しました。見逃した場合、または簡単に復習したい場合は、続行する前に気軽にチェックしてください。

このパートでは、もう 1 つの重要なパターンであるマルチポインター パターンについて詳しく説明します。このパターンは、複数の要素を同時に比較、検索、または走査する必要があるシナリオを扱う場合に非常に貴重です。これがどのように機能するのか、またコードの効率を向上させるためにどこに適用できるのかを見てみましょう。

02. マルチポインターパターン

マルチポインター パターン は、配列やリンク リストなどのデータ構造を横断するために複数のポインター (または反復子) を使用するアルゴリズム設計で使用される手法です。このパターンでは、単一のポインターまたはループに依存するのではなく、異なる速度または異なる開始点からデータ内を移動する 2 つ以上のポインターを使用します。

問題例

整数の sorted 配列を受け入れる sumZero という関数を作成します。関数は、合計がゼロである 最初のペア を見つける必要があります。そのようなペアが存在する場合は、両方の値を含む配列を返します。それ以外の場合は、未定義.
を返します。

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

基本的な解決策

function sumZero(arr){
    for (let i = 0; i 



時間計算量 - O(N^2)

マルチポインター パターンを使用した解決策

ステップ 1: 問題を理解する

**sorted 配列内で合計が 0 になる 2 つの数値を見つける必要があります。配列はソートされているため、この順序を利用して、より効率的に解を見つけることができます。

ステップ 2: 2 つのポインターを初期化する

2 つのポインターを設定します。1 つは配列の先頭から始まる (left)、もう 1 つは配列の末尾から始まる (right) です。

例：


Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5




ステップ 3: ポインターの値の合計を計算する

左右のポインタの値を加算して合計を取得します


Sum = -4   5 = 1




ステップ 4: 合計をゼロと比較します

• 合計がゼロより大きい場合: 右ポインタを 1 ステップ左に移動すると、合計が減少します。

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• 合計がゼロより小さい場合: 左ポインタを 1 ステップ右に移動すると、合計が増加します。

New Sum = -4   2 = -2
Sum is -2 



ステップ 5: プロセスを繰り返します

ポインタが一致するかペアが見つかるまで、ポインタを移動して合計を計算し続けます。


New Sum = -3   2 = -1
Sum is -1 



合計はゼロなので、関数は [-2, 2] を返します。

そのようなペアが見つからずにループが完了した場合は、unknown.
 を返します。

最終コード


function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left  0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left  ;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}




注記：
時間計算量: O(n) – この関数は効率的で、配列のサイズに応じて線形にスケールします。
空間複雑度: O(1) – この関数は最小限の追加メモリを使用します。

結論

マルチポインタ パターンは、並べ替えられたデータ構造内の要素の検索、比較、または操作を伴う問題を解決するための強力な手法です。互いに向かって移動する複数のポインターを使用することで、アルゴリズムの効率を大幅に向上させることができ、多くの場合、時間の複雑さを O(n²) から O(n) に削減できます。このパターンは汎用性が高く、幅広い問題に適用できるため、コードのパフォーマンスを最適化するために不可欠な戦略となります。

次の投稿にご期待くださいでは、動的データ セグメントに関係する問題に取り組むためのもう 1 つの重要なツールである スライディング ウィンドウ パターン について詳しく説明します。これは、さらに複雑な課題を簡単に解決できる非常に便利なパターンです!