arrays - 在具有所有唯一值的数组中搜索最短切片，如何以最佳方式执行此操作？

Question

我有一个包含 N 个元素的数组，这些元素的值在 0 <= value < N 范围内，并且可以是不连续的。对于这个数组，我需要找到一个包含所有唯一值的切片，同时它将是满足上述标准的最短切片。

例如，对于具有 5 个唯一值 {1, 2, 3, 4, 8} 的数组 {1, 2, 1, 2, 1, 4, 3, 4, 8, 1, 8}，我们正在讨论切片 {2 , 1, 4, 3, 4, 8} 长度为 6。

有没有最佳的方法来做到这一点？至于现在，我的实现过于复杂（嵌套循环）。我试图想出一个算法来以最佳方式做到这一点，但遗憾的是无济于事。至于现在，我试图想出一些东西，在遍历数组时利用每个唯一值的出现，但我的想法仍然不够清晰。欢迎任何想法，这个问题困扰了我很长时间。：） 先感谢您。

此致

Answer 1

第一次运行收集可能的值并创建一个带有对的映射(value; counter = 0)。让N是地图大小

为第二次运行准备两个索引 - leftand right, and ActiveCnt。

移动right，更新地图计数器。当您更新零计数器时，递增ActiveCnt. 当ActiveCnt等于 时N，停止。

现在移动left，减少地图计数器。right当某个计数器变为零时，获取and之间的差异left，将其与 current 进行比较MinLength，然后递减ActiveCnt。继续right索引等等。