JavaScriptで文字列配列の共通要素（積集合）を効率的に求める方法

JavaScriptでは、2つの配列に共通して含まれる要素（積集合）を求めたい場面がよくあります。本記事では、2つの文字列配列を受け取り、その共通部分を計算して新しい配列として返す intersection() 関数の実装方法を解説します。

結果の配列には、両方の配列に出現した回数だけ各要素を含める必要があります。順序は問いません。

例：入力と期待される出力

たとえば、以下のような入力があったとします。

arr1 = ['hello', 'world', 'how', 'are', 'you'];
arr2 = ['hey', 'world', 'can', 'you', 'rotate'];

この場合、出力は次のようになります。

Output: ['world', 'you'];

アプローチ

もし配列があらかじめソートされていれば、「2ポインタ法」を使うのが理想的です。それぞれの配列の先頭にポインタを置き、値を比較しながら該当するポインタを進めていくことで、時間計算量 O(m+n)（m、nはそれぞれの配列のサイズ）で処理できます。

しかし今回はソートされていない配列が対象です。わざわざソートしてから2ポインタ法を使うのは非効率です。そこで、片方の配列の各要素がもう片方の配列に存在するかどうかを順番に確認し、共通する要素だけを結果配列に追加していく方法を採用します。この方法の時間計算量は O(n²) となりますが、小〜中規模のデータであれば十分実用的です。

なお、同じ要素が複数回マッチしないよう、マッチ済みの要素は undefined に置き換えて再利用を防いでいます。

実装コード

以下が実際のコードです。短い方の配列を基準にループすることで、無駄な比較を減らしています。

arr1 = ['hello', 'world', 'how', 'are', 'you'];
arr2 = ['hey', 'world', 'can', 'you', 'rotate'];
const intersectElements = (arr1, arr2) => {
    const res = [];
    const { length: len1 } = arr1;
    const { length: len2 } = arr2;
    // 短い方の配列を基準にする
    const smaller = (len1 < len2 ? arr1 : arr2).slice();
    const bigger = (len1 >= len2 ? arr1 : arr2).slice();
    for(let i = 0; i < smaller.length; i++) {
        if(bigger.indexOf(smaller[i]) !== -1) {
            res.push(smaller[i]);
            // マッチした要素を使い切りにする（重複カウント防止）
            bigger.splice(bigger.indexOf(smaller[i]), 1, undefined);
        }
    };
    return res;
};
console.log(intersectElements(arr1, arr2));

実行結果

このコードを実行すると、コンソールには次のように出力されます。

[ 'world', 'you' ]

補足：より効率的な代替手段

パフォーマンスが重要なケースでは、Map や Set を使って要素の出現回数を事前に記録しておくことで、時間計算量を O(n+m) まで改善できます。大量のデータを扱う場合は、このハッシュベースのアプローチを検討するとよいでしょう。