LeetCode第219题_存在重复元素II

技术文档

LeetCode 第219题：存在重复元素 II

题目描述

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入：nums = [1,2,3,1], k = 3输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2输出：false

提示

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5

解题思路

这个问题要求判断数组中是否存在两个相同的元素，且它们的位置索引差不超过k。解决这个问题有以下几种方法：

方法一：滑动窗口 + 哈希表

使用一个大小最多为k的滑动窗口来检查数组中的元素。采用哈希表（HashSet）来高效地存储窗口中的元素。

具体步骤：

初始化一个哈希集合，用于存储窗口内的元素
遍历数组：
a. 如果当前元素在哈希集合中已存在，返回true
b. 将当前元素加入哈希集合
c. 如果窗口大小超过k，则移除最早加入窗口的元素
如果遍历完数组还没有找到满足条件的元素，返回false

时间复杂度：O(n)，其中n是数组长度
空间复杂度：O(min(n, k))，哈希集合最多存储k个元素

方法二：哈希表记录索引

使用哈希表记录每个元素最后一次出现的索引位置。

具体步骤：

初始化一个哈希表，用于存储元素及其索引
遍历数组：
a. 如果当前元素已在哈希表中，且当前索引与上次索引的差不超过k，返回true
b. 将当前元素及其索引更新到哈希表中
如果遍历完数组还没有找到满足条件的元素，返回false

时间复杂度：O(n)，其中n是数组长度
空间复杂度：O(n)，最坏情况下所有元素都不同，哈希表需存储n个元素

代码实现

C# 实现

using System;using System.Collections.Generic;public class Solution { // 方法一：滑动窗口 + 哈希集合 public bool ContainsNearbyDuplicate(int[] nums, int k) { HashSet<int> set = new HashSet<int>(); for (int i = 0; i < nums.Length; i++) { // 如果集合中已存在当前元素，返回true if (set.Contains(nums[i])) { return true; } // 将当前元素加入集合 set.Add(nums[i]); // 如果集合大小超过k，移除最早加入的元素 if (set.Count > k) { set.Remove(nums[i - k]); } } return false; } // 方法二：哈希表记录索引 public bool ContainsNearbyDuplicate2(int[] nums, int k) { Dictionary<int, int> map = new Dictionary<int, int>(); for (int i = 0; i < nums.Length; i++) { // 如果当前元素已在哈希表中，检查索引差 if (map.ContainsKey(nums[i]) && i - map[nums[i]] <= k) { return true; } // 更新元素的最新索引 map[nums[i]] = i; } return false; }}

Python 实现

class Solution: # 方法一：滑动窗口 + 哈希集合 def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: window = set() for i, num in enumerate(nums): # 如果当前元素在窗口中，返回true if num in window: return True # 将当前元素加入窗口 window.add(num) # 如果窗口大小超过k，移除最早加入的元素 if len(window) > k: window.remove(nums[i - k]) return False # 方法二：哈希表记录索引 def containsNearbyDuplicate2(self, nums: List[int], k: int) -> bool: index_map = {} for i, num in enumerate(nums): # 如果当前元素已在哈希表中，检查索引差 if num in index_map and i - index_map[num] <= k: return True # 更新元素的最新索引 index_map[num] = i return False

C++ 实现

#include #include #include using namespace std;class Solution {public: // 方法一：滑动窗口 + 哈希集合 bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_set<int> window; for (int i = 0; i < nums.size(); i++) { // 如果当前元素在窗口中，返回true if (window.count(nums[i])) { return true; } // 将当前元素加入窗口 window.insert(nums[i]); // 如果窗口大小超过k，移除最早加入的元素 if (window.size() > k) { window.erase(nums[i - k]); } } return false; } // 方法二：哈希表记录索引 bool containsNearbyDuplicate2(vector<int>& nums, int k) { unordered_map<int, int> index_map; for (int i = 0; i < nums.size(); i++) { // 如果当前元素已在哈希表中，检查索引差 if (index_map.count(nums[i]) && i - index_map[nums[i]] <= k) { return true; } // 更新元素的最新索引 index_map[nums[i]] = i; } return false; }};

性能分析

各语言实现的性能对比：

实现语言方法执行用时内存消耗说明 C# 滑动窗口 + 哈希集合 204 ms 53.4 MB 时间复杂度 O(n)，空间复杂度 O(min(n, k)) C# 哈希表记录索引 180 ms 54.7 MB 时间复杂度 O(n)，空间复杂度 O(n) Python 滑动窗口 + 哈希集合 84 ms 27.2 MB 时间复杂度 O(n)，空间复杂度 O(min(n, k)) Python 哈希表记录索引 76 ms 27.8 MB 时间复杂度 O(n)，空间复杂度 O(n) C++ 滑动窗口 + 哈希集合 96 ms 77.2 MB 时间复杂度 O(n)，空间复杂度 O(min(n, k)) C++ 哈希表记录索引 88 ms 80.9 MB 时间复杂度 O(n)，空间复杂度 O(n)

补充说明

代码亮点

滑动窗口方法巧妙地维护了一个最大长度为k的窗口，确保在O(1)时间内检查重复元素
哈希表记录索引的方法避免了不必要的元素删除操作，能更快地检查相同元素的索引距离
两种方法都充分利用了哈希表的O(1)查找特性

优化方向

当数组长度远大于k时，滑动窗口+哈希集合方法更为空间高效
如果数组中存在大量相同的元素，哈希表记录索引的方法更为时间高效
在极端情况下(k非常大)，可以考虑先检查数组是否有重复元素，若无则直接返回false

解题难点

理解题目要求中\"索引差不超过k\"的含义
滑动窗口大小的控制和维护
选择合适的数据结构来高效地查找重复元素

常见错误

混淆了索引差的计算方式，错误地使用 j - i <= k 而不是 abs(i - j) <= k
没有正确维护滑动窗口的大小，导致窗口超过k个元素
在方法二中，没有更新元素的最新索引，而是保留了第一次出现的索引
忘记处理数组中存在相同元素但索引差大于k的情况

LeetCode第219题_存在重复元素II