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

Question

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

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

有没有最佳的方法来做到这一点？至于现在，我的实现过于简单(嵌套循环)。我试图想出一个算法的想法，以最佳方式做到这一点，但遗憾的是无济于事。至于现在，我已经尝试想出一些方法，在遍历数组时使用每个唯一值的出现次数，但我的想法仍然不够清晰。欢迎任何想法，这个问题困扰了我很长时间。 :) 在此先感谢您。

最好的问候

Answer 1

第一次运行收集可能的值并创建一个包含对(value; counter = 0) 的映射。设 N 为 map 大小

为第二次运行准备两个索引 - left 和 right，以及 ActiveCnt。

向右移动，更新 map 计数器。当您更新零计数器时，增加 ActiveCnt。当ActiveCnt等于N时，停止。

现在向左移动，递减 map 计数器。当某个计数器变为零时，获取right和left之间的差异，将其与当前MinLength进行比较，然后递减ActiveCnt .继续 right 索引等等。