arrays - 返回数组中给定窗口大小内的重复项？

Question

我看到了这个问题，但由于时间和空间的限制，我不知道如何做第二部分：

给定一个值数组，设计并编写一个算法，该算法返回在彼此的 k 个索引内是否有两个重复项？k个索引并且在彼此的正负l（值）之内？在 O(n) 运行时间和 O(k) 空间内完成所有工作，即使是后者。

如果不查看 k 和 a[i] 之间索引差异的所有值，我似乎不可能知道在值的窗口大小内是否存在给定值的副本，但由于 a[i] 可能很大，我认为这将需要 O(n^2)。可以在 O(n) 中完成吗？

Answer 1

这听起来有点像家庭作业。是的，它可以在 O(n) 时间和 O(k) 空间内完成。提示：您需要两个数据结构，其中一个是哈希映射。