13. Intersection of Two Arrays

読了目安約1分

HashMap / LeetCode 349 (Easy) — 集合の intersection で 2 つの配列の共通要素を重複なく取り出す。

この章の目次

問題

LeetCode 349. Intersection of Two Arrays（Easy / カテゴリ: HashMap）

2 つの整数配列 nums1 と nums2 が与えられます。両方に登場する値だけを、重複なしで返します。返す順序は自由です。

考え方

ヒント 1

配列のまま contains で調べると、判定 1 回に O(n) かかります。「含まれているか」を速く調べられるデータ構造に変換してから比べます。

ヒント 2

両方を集合（Set）にすれば、重複が消え、共通部分を取る操作がそのまま答えになります。

Swift 実装のポイント

Set(nums1) で配列から集合を作れます。重複はこの時点で消えます。
共通部分は set1.intersection(set2) で取れます。
Array(...) で配列に戻すと順序は不定です。テストコードはソートしてから比較します。

模範解答

Swift
class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        let set1 = Set(nums1)
        let set2 = Set(nums2)
        return Array(set1.intersection(set2))
    }
}

計算量: O(n + m)（2 つの配列をそれぞれ 1 回ずつ処理します）。