集合の積 (intersection)｜コードで実践

集合の積 (intersection)

このレッスンで分かること

2 つの配列 a, b の 両方に含まれる要素 を集めることを「集合の積 (intersection)」と呼びます

関数 setIntersection(a, b) は次を満たします

例として a = [1, 2, 2, 3], b = [2, 3, 4] なら戻り値は [2, 3]

集合の積とは

2 つの整数配列の共通要素 (集合の積) を set で求めて、重複なしの昇順リストで返す。本レッスンでは、集合の積の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

2 つの配列 a, b の 両方に含まれる要素 を集めることを「集合の積 (intersection)」と呼びます。これは set の代表的な使い道のひとつで、データベースの JOIN、ユーザーのフォロー関係の共通フォロワー、SNS のタグの絞り込みなど、実務でも頻繁に登場します。本レッスンでは set の集合演算を O(n + m) で書く方法を学びます。

集合演算 (積 / 和 / 差) は set の真骨頂。リスト同士で書くと二重ループ O(n*m) だが、set を使えば O(n + m)。

仕様

関数 setIntersection(a, b) は次を満たします。

整数配列 a と b を受け取る (重複を含む可能性あり)
a にも b にも含まれる要素を集めて返す
戻り値は 重複なし かつ 昇順ソート済み のリスト
共通要素がなければ空配列 []

例として a = [1, 2, 2, 3], b = [2, 3, 4] なら戻り値は [2, 3]。

素朴な O(n*m) 解

Python

def setIntersection(a, b):
    result = []
    for x in a:
        if x in b and x not in result:
            result.append(x)
    result.sort()
    return result

x in b がリスト走査で O(m)、x not in result も O(k)。合計 O(n*m) 程度です。

O(n + m) アルゴリズム

a を set に入れ、b を 1 回走査して set に含まれるものを別 set に追加します。最後に昇順ソートしてリストとして返します。

diagram (will load when visible)

Python での実装

Python

def setIntersection(a, b):
    sa = set(a)
    result = set()
    for x in b:
        if x in sa:
            result.add(x)
    return sorted(result)

Python には set & set という演算子もあり、sorted(set(a) & set(b)) の 1 行でも書けます。ただし学習目的では明示的にループする実装を理解しておくのが大事です。

JavaScript での実装

JavaScript

function setIntersection(a, b) {
  const sa = new Set(a);
  const result = new Set();
  for (const x of b) {
    if (sa.has(x)) result.add(x);
  }
  return [...result].sort((x, y) => x - y);
}

JS でも Set がそのまま使えます。[...result] でリストに変換してから整数比較関数つきの sort をかけます。sort() だけだと文字列比較になるので注意。

Java での実装

Java

import java.util.*;

public class Solution {
    public static int[] setIntersection(int[] a, int[] b) {
        Set<Integer> sa = new HashSet<>();
        for (int v : a) sa.add(v);
        Set<Integer> result = new TreeSet<>();
        for (int v : b) {
            if (sa.contains(v)) result.add(v);
        }
        int[] arr = new int[result.size()];
        int i = 0;
        for (int v : result) arr[i++] = v;
        return arr;
    }
}

TreeSet は自動で昇順に並ぶ set なので、ソートする手間が省けます。最後に int[] に詰め直して返します。

Go での実装

import "sort"

func setIntersection(a []int, b []int) []int {
    sa := map[int]bool{}
    for _, v := range a {
        sa[v] = true
    }
    seen := map[int]bool{}
    result := []int{}
    for _, v := range b {
        if sa[v] && !seen[v] {
            seen[v] = true
            result = append(result, v)
        }
    }
    sort.Ints(result)
    return result
}

集合演算の一覧

余裕があれば次の演算も set で書けるようにしておきましょう。

和集合 (union): a | b (どちらかに含まれる)
差集合 (difference): a - b (a のみ)
対称差 (symmetric difference): a ^ b (どちらか一方のみ)
積集合 (intersection): a & b (両方に含まれる) ← 本問

これらはすべて O(n + m) で実装できます。

よくある間違い

1 つ目は 戻り値の順序忘れ。set から取り出した順は実装依存です。Python の set も Go の map も「挿入順 = 出力順」ではないので、必ずソートしてから返してください。
2 つ目は 重複を残してしまう。a = [1, 2, 2, 3], b = [2, 2, 4] で [2, 2] を返すバグはよくあります。set を使えば自動的に防げます。
3 つ目は JS sort の文字列比較。[10, 2, 1].sort() が [1, 10, 2] になる罠は何度でも復習しましょう。

集合系の問題では「順序」「重複」「空集合」の 3 つのエッジを必ず先に確認する。

やってみよう

同じ仕組みで 和集合 を返す関数 setUnion(a, b) を書いてみる (戻り値は昇順ソート済み)。
対称差 (a と b のどちらか片方のみ) を返す関数も書いてみる。
3 つ以上の配列の積集合に拡張する場合、どう書くと綺麗かを考える (reduce 風の畳み込みが綺麗)。

集合演算は配列・hashmap と同じく、面接でもサービス実装でも基本中の基本。一度自分の手で書けると次に応用できる。

よくある質問

Q. この内容は面接でよく聞かれますか？

A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。

Q. 計算量と空間計算量はどっちを優先しますか？

A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。

Q. 問題が解けないときどう取り組めば良いですか？

A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。

次のレッスン

次は 第4章まとめクイズ で、この章で学んだハッシュとセットの計算量・性質・使いどころを 4 択クイズで総点検します。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

集合の積の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 集合の積とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

集合の積 (intersection)