###### tags: `Leetcode` `easy` `hash` `python` `c++`

# 219. Contains Duplicate II

## [題目連結:] https://leetcode.com/problems/contains-duplicate-ii/

## 題目:
Given an integer array nums and an integer k, return true if there are two **distinct indices** i and j in the array such that nums[i] == nums[j] and abs(i - j) <= 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

## 解題想法:
兄弟題目: [217. Contains Duplicate](/96TcyffnSMO9yyt8OP_k2w)

* 使用一個hash table dic存放出現過的數字以及位置
* 判斷目前位置與dic儲存的位置距離是否小於等於k

## python:

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        dic={}
        for pos,val in enumerate(nums):
            if val in dic:
                if pos-dic[val]<=k:
                    return True
            dic[val]=pos
        return False

result=Solution()
ans=result.containsNearbyDuplicate(nums = [1,2,3,1], k = 3)
print(ans)

## C++:

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> dic;
        for (int i=0; i<nums.size(); i++){
            if (dic.find(nums[i])!=dic.end() && i-dic[nums[i]]<=k)
                return true;
            dic[nums[i]]=i;
        }
        return false;
    }
};

int main(){
    vector<int> nums={1,2,3,1};
    int k=3;
    Solution res;
    bool ans =res.containsNearbyDuplicate(nums,k);
    cout<<ans<<endl;
    return 0;
}