LeetCode 第219题 Contains Duplicate II

来源： https://leetcode.com/problems/contains-duplicate-ii/

给定一个数组，以及一个数字k，找到是否存在两个不重复的索引i，j，满足 nums[i] = nums[j] ，同时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 思路接近，但是难度加大了一些。我首先排除一些意外条件（k=0必然没有结果，数组大小小于2也是。如果k比数字的长度还大，那么就没有意思了，让k等于数组的长度。）：

然后，我们考察前k个元素，如果中间出现了重复，则直接返回true。如果考察完了前k个元素，没有重复，同时k与数组大小相等，那么直接可以返回false。

然后我们从k+1出发，构建一个定长的滑动窗口，每移动一格在hashset去掉一个之前的数字，加上一个当前的数字，在过程中发现了重复则返回true，如果全部遍历完，没有重复则可以返回false。

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

本文假设你对滑动窗口概念有所了解，如果你对滑动窗口的概念不够了解，请参看我介绍 滑动窗口的文章，里面有详细的解释 。

本题属于哈希表类题目，想了解更多关于哈希表的题目，可以参看哈希表专题。