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

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

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

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据