【PHP】Two Sumアルゴリズムのパフォーマンス最適化

PHPでTwo Sumアルゴリズムにチャレンジ

あらかじめ用意された配列から、2つの数値の合計が決められた目標値になるように取り出し、その2つのインデックスを返す「Two Sum」というアルゴリズム問題にPHPでチャレンジしました。

一つ目にarray_searchを使った解き方を解説し、二つ目にハッシュマップを使ったより最適な実装方法について解説します。

array_searchを使った解き方（O(n²)）

function twoSum($target, $nums) {
    $map = [];
    
    foreach ($nums as $i => $num) {
        $need = $target - $num;
        
        $found_i = array_search($need, $map);
        
        if ($found_i !== false) {
            return [$found_i, $i];
        }
        $map[$i] = $num;
    }
}

この実装の問題点

• array_search()は内部で線形探索（O(n)）を行います
• ループと組み合わせると、全体の計算量は最悪の場合O(n²)になります
• 大きな配列では著しくパフォーマンスが低下します

ハッシュマップを使ったより最適な実装（O(n)）

function twoSum($target, $nums) {
    $map = [];  // numsの値をキー、numsのインデックスを値とするハッシュマップを作成
    
    foreach ($nums as $i => $num) {
        $need = $target - $num;
        
        // 補完値がすでに見つかっていればペアを返す
        if (isset($map[$need])) {
            return [$map[$need], $i];
        }
        
        // 現在の値とインデックスをマップに保存
        $map[$num] = $i;
    }
    
    return null;  // ペアが見つからない場合
}

最適化のポイント

• ハッシュテーブル（連想配列）を使って値→インデックスのマッピングを作成
• isset()による検索は定数時間O(1)
• ループが1回だけなので全体の計算量はO(n)
• メモリ使用量は増えますが、速度の向上が大きなメリット

パフォーマンス比較

実装	時間計算量	空間計算量
array_search()	O(n²)	O(n)
ハッシュテーブル	O(n)	O(n)

まとめ

データ構造を適切に選ぶことで、アルゴリズムの効率を劇的に改善できます。Two Sumのような問題では、配列の線形探索ではなく、ハッシュテーブルを活用することで計算量を大幅に削減できます。

これは、「空間を使って時間を買う」という一般的なトレードオフの好例です。メモリ使用量は増えますが、実行速度が大幅に向上します。