# 3.Contains Duplicate

## Type I:

Given an array of integers, find if the array contains any duplicates.\
Your function should **return true if any value appears at least twice in the array**, and it should **return false if every element is distinct.**

```
Example 1:
Input: nums = [1,2,3,1]
Output: true

Example 2:
Input: nums = [1,2,3,4]
Output: false

Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
```

### Solution: (Using Hash set)

```
Example 1:
Input: [1,2,3,1]
Output: true

Example 2:
Input: [1,2,3,4]
Output: false
```

```cpp
class Solution
{
public:
    bool containsDuplicate(vector<int> &nums)
    {

        if (nums.size() == 0)
        {
            return false;
        }

        unordered_set<int> s;
        bool res = false;
        for (int i = 0; i < nums.size(); i++)
        {
            if (s.find(nums[i]) == s.end())
            {
                s.insert(nums[i]);
            }
            else
            {
                res = true;
                break;
            }
        }

        return res;
    }
};
```

## Type II:&#x20;

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that **nums\[i] = nums\[j]** and the **absolute** difference between i and j is at most k.

```
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true


Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
```

### Solution: (Using Hashmap)

```
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
```

**Solution :**

```cpp
class Solution
{
public:
    bool containsNearbyDuplicate(vector<int> &nums, int k)
    {

        unordered_map<int, vector<int>> m;
        bool res = false;
        for (int i = 0; i < nums.size(); i++)
        {

            if (m.find(nums[i]) == m.end())
            {
                vector<int> v;
                v.push_back(i);
                m.insert({nums[i], v});
            }
            else
            {
                auto itr = m.find(nums[i]);
                vector<int> v;
                v = itr->second;
                v.push_back(i);
                m[nums[i]] = v;
            }
        }

        for (auto itr = m.begin(); itr != m.end(); itr++)
        {
            vector<int> v = itr->second;

            if (v.size() > 0)
            {
                int i = 0;
                while (i < v.size() - 1)
                {
                    if (v[i + 1] - v[i] <= k)
                    {
                        res = true;
                        break;
                    }
                    i++;
                }
            }
        }

        return res;
    }
};
```