目录
问题描述
输入输出格式
示例
算法分析
过题图片
代码实现
复杂度分析
题目链接
总结
问题描述
给定一个整数数组nums和一个整数k，我们需要判断数组中是否存在两个不同的索引i和j，使得nums[i] == nums[j]且|i - j| <= k。如果存在这样的i和j，返回true；否则，返回false。
输入输出格式
- 输入：一个整数数组
nums和一个整数k。 - 输出：一个布尔值，表示是否存在满足条件的
i和j。
示例
- 输入：
nums = [1,2,3,1],k = 3，输出：true。 - 输入：
nums = [1,0,1,1],k = 1，输出：true。 - 输入：
nums = [1,2,3,1,2,3],k = 2，输出：false。
算法分析
这个问题可以通过使用哈希表来解决。我们需要跟踪最近k个元素，检查是否有任何重复的元素出现。以下是解决这个问题的步骤：
- 创建一个
HashSet来存储最近k个元素。 - 遍历数组
nums，对于每个元素：- 检查该元素是否已经在
HashSet中。如果是，返回true。 - 将当前元素添加到
HashSet中。 - 如果
HashSet的大小超过了k，从HashSet中移除最老的元素（即在i - k位置的元素）。
- 检查该元素是否已经在
- 如果遍历结束后没有找到重复元素，返回
false。
过题图片
代码实现
java
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {HashSet<Integer> set = new HashSet<>();for(int i = 0; i < nums.length; i++) {if(set.contains(nums[i])) {return true;}set.add(nums[i]);if(set.size() > k) {set.remove(nums[i - k]);}}return false;}
}C++
class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_set<int>set;for(int i=0;i<nums.size();++i){if(set.count(nums[i])){return true;}set.emplace(nums[i]);if(set.size()>k){set.erase(nums[i-k]);}}return false;}
};复杂度分析
- 时间复杂度：O(n)，其中n是数组
nums的长度。我们只需要遍历一次数组。 - 空间复杂度：O(min(n, k))，在最坏的情况下，我们需要存储所有元素，但在大多数情况下，我们只需要存储最近
k个元素。
题目链接
219. 存在重复元素 II - 力扣（LeetCode）
总结
这个问题是一个典型的使用哈希表解决的问题，它考察了我们对哈希表操作的理解和应用。通过维护一个滑动窗口内的元素集合，我们可以有效地检查是否存在满足条件的重复元素。这种方法简洁且高效，是解决这类问题的首选方法。此外可以通过这道题看一下其他应用
哈希表的应用
哈希表（或称为散列表）是一种通过键值对存储数据的数据结构，它能够提供快速的查找、插入和删除操作。在这个问题中，哈希表的使用展示了其在处理数组和集合问题中的强大能力。通过将元素的值作为键，我们可以在常数时间内检查元素是否已经存在于哈希表中，从而避免了复杂的遍历和比较操作。
滑动窗口技术
滑动窗口是一种处理数组子区间问题的有效技术。在这个问题中，我们维护了一个大小为k的窗口，随着数组的遍历，窗口内的元素集合也在不断更新。这种技术允许我们只关注数组中与当前元素距离不超过k的元素，从而简化了问题。
时间和空间效率
我们的方法具有线性时间复杂度O(n)，其中n是数组的长度。这是因为我们只需要遍历一次数组，并且在哈希表中进行的操作（插入、删除和查找）都是常数时间的。空间复杂度为O(min(n, k))，这是因为在最坏的情况下，我们可能需要存储所有元素，但在大多数情况下，我们只需要存储最近k个元素。
代码实现的简洁性
我们的代码实现简单而直观，易于理解和实现。这种方法不仅减少了代码的复杂性，也降低了出错的可能性。通过将逻辑封装在一个循环中，我们避免了复杂的条件判断和多个循环的嵌套。
算法的适用性
这种方法不仅适用于本问题，还可以推广到其他需要检测数组中重复元素的场景，特别是那些涉及到元素之间距离限制的问题。例如，它可以用于检测一个数组中是否存在两个元素，它们的差值不超过某个给定的阈值。
算法的局限性
尽管这种方法在大多数情况下都非常有效，但它也有局限性。例如，如果数组中的元素数量远远大于k，那么维护一个固定大小的窗口可能不是最优的选择。此外，如果数组中的元素值范围非常大，哈希表可能会消耗大量的内存。
