检查给定数组是否包含相距 k 以内的重复元素

根据问题“检查给定数组中相距 k 以内的重复元素”，我们必须确定提供的无序数组中是否存在相距 k 以内的重复元素。在此实例中，提供的数组无法容纳 k 的值。

K=2，所以我们看到一个包含两个 1 的窗口。该数组包含一个大小为 k 的包含重复项的窗口。

示例

示例-1

输出

False

示例-2

输出

True

示例-3

输出

False

示例 4

输出

True

说明

要解决这个问题，我们有两种选择。更简单的方法是执行两个循环，第一个循环选择每个元素作为第二个循环的起始元素，称为“内循环”。然后，第二个循环会将起始元素与“k”范围内的每个元素进行比较。但是，这种方法效率不高；其时间复杂度为 O(k*n)。

哈希是更有效的一种技术，可以解决这个问题，时间复杂度为 O(n)。在哈希技术中，我们将遍历数组的项以确定元素是否存在。如果元素存在，我们将返回“True”。如果不存在，我们将将其添加到哈希中，并且如果 i 大于或等于 k，我们将从哈希中移除 arr[i-k] 元素。

检查算法以确定给定数组是否包含相互距离 k 以内的重复元素

• 首先创建空的哈希集，然后将数组的元素添加到其中。
• 从左到右遍历数组的整个元素集。
• 验证该元素是否包含在哈希中。
  • 如果包含，则返回“true”。
  • 如果不存在，则将该元素包含在哈希中。
• 之后，如果“i”大于或等于“k”，则从哈希中移除 arr [i-k] 元素。

我们将使用哈希集来存储其中的元素，一次添加数组的每个元素。如果元素已存在于哈希集中，它将返回 true 并结束循环。如果不存在，它将继续将元素添加到集合中并从集合中移除 arr[i-k] 元素。我们有一个名为“arr []”的数组，其中包含一些元素，以及一个值 k，它表示我们必须在该范围内查找重复项（如果存在）。

代码

检查 C++ 代码中数组内距离 k 以内的重复元素

输出

Yes

检查 Java 中数组内距离 k 以内的重复元素

输出

Yes

复杂性评估

时间复杂度

O (n)，其中“n”是数组的总元素数。通过使用哈希集，该问题可以线性解决。因为使用哈希集可以提高搜索、删除和数据插入的效率。

空间复杂度

O (k)，其中“k”表示必须检查的窗口元素数量。