arrays - 包含所有元素而不使用数组的最短子数组？

Question

问题:找到包含所有元素的最短子数组的长度示例:1 2 2 3 2 2 1 3答案:3

我读到过，解决此问题的最佳方法是使用滑动窗口方法。但是这种方法需要使用数组。有没有其他不需要通过存储每个元素的出现次数来使用数组的有效方法？ (我想通过在 ML 中编写它来使用这种没有数组的方法)

Answer 1

我假设您想避免使用数组的原因是您希望编写惯用 ML 代码，因此更愿意使用纯函数数据结构而不是可变数组？

如果是这样，那么您可以使用 purely functional red-black tree对于“滑动窗口”方法，几乎​​与使用数组的方式完全相同；唯一的区别是:

• 不是 O(1) 次查找，而是 O(log m) 次查找，其中 m是不同元素的数量。
• 不是 O(1) 个突变，而是 O(log m) 个转换，其中转换返回 map (共享其大部分节点)。