跳至主要內容

219. 存在重复元素 II


219. 存在重复元素 IIopen in new window

🟢   🔖  数组 哈希表 滑动窗口  🔗 力扣open in new window LeetCodeopen in new window

题目

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 ,判断数组中是否存在两个 不同的索引 ij ,满足 nums[i] == nums[j]abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false

解题思路

可以使用滑动窗口来解决这道题,维护一个只有 K 个元素的 mapmap 的长度如果超过了 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存在重复元素open in new window[✓]数组 哈希表 排序
220存在重复元素 IIIopen in new window数组 桶排序 有序集合 2+