[leetcode_217] Contains Duplicate

Determine whether a given array contains duplicate elements. A hash table solves this. I actually used a map, which is a binary search tree in C++. The O(log n) solution, so the performance isn’t the best.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        map<int, bool> m_nums;
        m_nums.clear();
        for (int i = 0; i < nums.size(); i++)
        {
            map<int, bool>::iterator it = m_nums.find(nums[i]);
            if (it == m_nums.end())
            {
                m_nums.insert(map<int, bool>::value_type(nums[i], true));
            }
            else
            {
                return true;
            }
        }
        return false;
    }
};