# LeetCode Easy 217. Contains Duplicate

tags: leetcode

めちゃくちゃ久々に問題を解きます．

関係ないですが，インターン2社行くことになりそうです^^

問題

• Explore
• Problems

アイデア

配列内に複数回出てくる数があるかどうかを探せという問題です．

これは連想配列を使えば簡単に解くことが出来ます．問題は適切なデータ構造を知っているかどうかです．

解法

• keyに配列の要素，valueに配列の要素があるかどうかという二値を持つ連想配列mpを用意します．
• 配列を走査します
  • 要素がmpにあればtrueを返します．
  • なければその要素をkeyとする連想配列のvalueをtrueとします．
• 走査してもtrueを返さない場合はfalseとします．

計算量

配列の長さを$N$とします．

• 時間計算量
  • 配列を全て走査するので$O(N)$
• 空間計算量
  • 配列の要素が全て異なる場合，連想配列の大きさは$N$となるから，$O(N)$

C++

class Solution {
public:
  bool containsDuplicate(vector<int>& nums) {
    unordered_map<int, bool> mp;
    for (auto& num : nums) {
      if (mp[num]) {
        return true;
      }
      mp[num] = true;
    }
    return false;
  }
};