Source: https://leetcode.com/problems/contains-duplicate-ii/

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 = 3Output:true

**Example 2:**

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

**Example 3:**

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

This problem is similar to 217. Contains Duplicate, but a little harder. First we rule out some conditions (If k==0, must return false. if nums.length<2 must return false. And if k>nums.length we need let k=nums.length.) :

Then, we look at first k elements, if there is a duplicate, then return true. If k==nums.length, but we don’t find any duplicate return false.

Then we start from k+1, build a fixed-width sliding window. Every time we move one postion, we remove the oldest number from the window, add the new number in the window. In this process, if we find a duplicate return true. When all numbers are checked, we still can’t find a duplicate return false.

Github：https://github.com/tinyfool/leetcode/tree/master/src/p0219

Want to know details of the sliding window algorithm, check my post: The Sliding Window Algorithm for string and array.

To see more hashtable related problems, see

Problems and Solutions of Hashmap.