# LeetCode Easy 349. Intersection of Two Arrays

tags: leetcode

問題

• Explore
• Problems

アイデア

2つの配列のintersection(交叉･共通部分)を求めよという問題．

このような問題ではsetを使うと楽に求めることが可能です

解法

• nums1をstd::unordered_setに変換します
  • std::unordered_setはハッシュ，std::setは二分木で実装されています．
• nums2の要素がこの集合の要素に入っているときこれを答えとなる配列に入れます．

計算量

2つの配列の長さをそれぞれN，Mとします．

• 時間計算量
  • nums1をstd::setに変換するのに$O(N)$
  • nums2を全探索するのに$O(M)$
  • std::unordered_setへの要素の挿入，削除は$O(1)$だから
  • $O(N+M)$
• 空間計算量
  • num1をstd::unordered_setに変換するのに$O(N)$
  • 答えとなる配列の大きさは最大で$O(N)$
  • よって$O(N)$

C++

class Solution {
public:
  vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> set1(nums1.begin(), nums1.end());
    vector<int> res;
    for (auto& n : nums2)
      if (set1.erase(n))
        res.push_back(n);
    return res;
  }
};