41
LeetCode 第219题 Contains Duplicate II
source link: https://www.tuicool.com/articles/qYjInen
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
来源： https://leetcode.com/problems/contains-duplicate-ii/
给定一个数组，以及一个数字k，找到是否存在两个不重复的索引i，j，满足 nums[i] = nums[j] ，同时i和j之间位置的差距在k以内。
Example 1:
<strong>Input: </strong>nums = [1,2,3,1], k = 3 <strong>Output: </strong>true
Example 2:
<strong>Input: </strong>nums = [1,0,1,1], k = 1 <strong>Output: </strong>true
Example 3:
<strong>Input: </strong>nums = [1,2,3,1,2,3], k = 2 <strong>Output: </strong>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
本文假设你对滑动窗口概念有所了解，如果你对滑动窗口的概念不够了解，请参看我介绍 滑动窗口的文章，里面有详细的解释 。
本题属于哈希表类题目，想了解更多关于哈希表的题目，可以参看哈希表专题。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK