Guppi StudioPROBLEM 03
2つの配列に共通する値
2つの配列に現れる値を、重複なしで返します。
2つの参加者リストを数値IDで受け取ります。 両方のリストに登場するIDだけを、重複を取り除いて返してください。 返す順番は問いません。
例
入力: left = [2, 2, 4, 8], right = [1, 2, 2, 8]
出力: [2, 8]
理由: 両方に現れるのは 2 と 8。left に 2 が2回あっても、出力には1回だけ入力: left = [1, 3, 5], right = [2, 4, 6]
出力: []制約
- 各配列の長さは
0以上50,000以下 - 要素は安全な整数
- 出力に同じ値を2回含めない
- 目標: O(n + m) 相当（
includesの繰り返しは性能テストで時間切れになります）
対応する問題: LeetCode #349 Intersection of Two Arrays
まず素朴に解くと — includes で毎回探す
「left の各値が right にあるか調べる」をそのまま書くとこうなります。
function intersection(left: number[], right: number[]): number[] {
const result: number[] = [];
for (const value of left) {
if (right.includes(value) && !result.includes(value)) {
result.push(value);
}
}
return result;
}right.includes(value) は配列を先頭から線形に探すので、1回あたり O(m)。さらに result.includes でも探し直しています。全体では O(n × m) です。
どこが遅いのか
性能テストは各 50,000 要素です。includes の繰り返しは最悪 25億回 の要素アクセスになります。配列の includes は「呼ぶたびに端から探し直す」ため、同じ質問を何万回も投げ直しているのが遅さの正体です。
発想の転換
「あるかどうか」を配列に聞くのをやめて、先に存在の索引を作る。
JavaScript の Set は「その値が入っているか」を平均 O(1) で答えるデータ構造です。right を一度だけ Set に変換しておけば、以降の存在確認はすべて定数時間になります。結果側も Set にすれば、重複の除去まで同時に片づきます。
解答例 — O(n + m)
function intersection(left: number[], right: number[]): number[] {
const rightValues = new Set(right);
const common = new Set<number>();
for (const value of left) {
if (rightValues.has(value)) common.add(value);
}
return [...common];
}動きを追う — left = [2, 2, 4, 8], right = [1, 2, 2, 8]
前準備: rightValues = Set{1, 2, 8}（Set なので right 内の重複 2 は1つになる）
| value | rightValues にある？ | common |
|---|---|---|
| 2 | ある | {2} |
| 2 | ある | {2}（Set なので増えない） |
| 4 | ない | {2} |
| 8 | ある | {2, 8} |
出力は [2, 8]。2回目の 2 を特別扱いするコードを書かなくても、Set の性質が重複除去を肩代わりしてくれています。
計算量の比較
| 解法 | 時間 | 追加領域 | 各 50,000 要素での目安 |
|---|---|---|---|
| includes の繰り返し | O(n × m) | O(1) | 最大25億アクセス |
| Set 化して1周ずつ | O(n + m) | O(n + m) | 約10万操作 |
面接でどう話すか
「
includesを繰り返すと O(n×m) になるので、まず right を Set に変換して存在確認を O(1) にします。結果も Set に集めれば重複除去が自動で済み、全体は O(n+m) です。」
Array.includes / indexOf がループ内に現れたら計算量が1段上がっている合図 — このアンチパターンに自分で気づけると、コードレビューでも面接でも強い武器になります。
STEPWISE HINTS
ヒント
01最初の一手
片方の配列に値が含まれるかを、もう片方から何度も調べる処理を高速化します。
02処理の組み立て
Set を使うと、値の存在確認と重複の除去を同時に扱えます。
03コードの形
right を Set にする。left の各値を調べ、right に存在する値を結果用 Set に追加して、最後に配列へ変換する。
AFTER ACCEPTED
解説
まずは自分の言葉で方針を説明し、コードに落としてみましょう。