JavaScriptで2つの配列の共通要素（交差）を求める方法

問題の概要

2つの数値の配列が与えられたとき、それらの共通部分（交差）を計算し、共通する要素を含む配列を返す関数 intersection() を作成します。結果の配列内の各要素は、両方の配列に出現する回数だけ含まれる必要があります。要素の並び順は問いません。

例えば、次のような入力と出力になります。

入力: arr1 = [1,2,3,1], arr2 = [1,3,1]
出力: [1,3,1]

アプローチ

もし配列があらかじめソートされていれば、「ツーポインタ法」が有効です。2つのポインタをそれぞれの配列の先頭（インデックス0）に置き、値を比較しながら対応するポインタを進めていくことで、O(m+n) の時間計算量で解くことができます（m と n はそれぞれの配列のサイズ）。

しかし、今回は配列がソートされていないため、わざわざソートしてからこの手法を適用するのは非効率です。そこで、片方の配列の各要素をもう片方の配列に対して順番に照合し、一致した要素を結果の配列に追加していく方法を採用します。この方法の時間計算量は O(n²) となります。

実装例

const arr1 = [1, 2, 43, 5, 3, 7, 7, 8, 4, 2];
const arr2 = [1, 1, 6, 6, 2, 78, 7, 2, 3, 7, 23, 5, 3];

const intersection = (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]);
            // 一致した要素をundefinedに置き換え、重複マッチを防止
            bigger.splice(bigger.indexOf(smaller[i]), 1, undefined);
        }
    }
    return res;
};

console.log(intersection(arr1, arr2));

コードのポイント

• 短い方の配列を基準にループ： 要素数の少ない配列側を走査対象にすることで、無駄な比較を減らしています。
• 重複の制御： 一致した要素を splice() で undefined に置き換えることで、同じ要素が複数回マッチするのを防ぎ、「両方の配列に出現する回数だけ」結果に含まれるという要件を満たしています。
• 元の配列を保護： slice() でコピーを作成しているため、元の配列は変更されません。

出力結果

コンソールには以下のように出力されます。

[1, 2, 5, 3, 7, 7, 2]