219. 存在重复元素 II
219. 存在重复元素 II
题目
Given an integer array nums
and an integer k
, return true
_if there are two distinct indices _i
andj
in the array such thatnums[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
Constraints:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5
题目大意
给你一个整数数组 nums
和一个整数 k
,判断数组中是否存在两个 不同的索引 i
和 j
,满足 nums[i] == nums[j]
且 abs(i - j) <= k
。如果存在,返回 true
;否则,返回 false
。
解题思路
可以使用滑动窗口来解决这道题,维护一个只有 K
个元素的 map
,map
的长度如果超过了 K
以后就删除掉第 i-k
的那个元素,这样一直维护 map
里面只有 K
个元素。
每次只需要判断这个 map
里面是否存在当前元素,如果存在就代表重复数字的下标差值在 K
以内。
代码
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function (nums, k) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
if (map.has(nums[i])) return true;
map.set(nums[i], 1);
if (map.size > k) map.delete(nums[i - k]);
}
return false;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
217 | 存在重复元素 | [✓] | 数组 哈希表 排序 | |
220 | 存在重复元素 III | 数组 桶排序 有序集合 2+ |