寻找具有不同值的最短子数组的算法

Question

给定一个数组A，找到一个最短的子数组Ai :J，使得A中存在的每个不同的值也存在于子数组中。

这个问题不是用来做作业的。这是一个关于哈希表的章节中的练习题。我不是在找代码。只是寻找算法或提示。

Answer 1

使用哈希表来维护字符串中每种类型元素的计数。

当你找到一个新类型的元素时，丢弃所有以前的答案，并开始修剪子字符串的开头，当你不能再修剪它时，如果一种类型的元素没有零，请记住这个子串，如果它是迄今为止找到的最短的，然后开始寻找另一个元素来取代你将要丢失的那个元素，或者找到一个以前没有见过的新元素。

当你到达字符串的末尾时，你就完成了。

如果你的散列是好的，这应该是O(n)

Answer 2

1-维护哈希表元素->计数

2-从头到尾遍历数组，递增元素计数。每当一个元素计数从0变为1时，在一个变量中记录它的索引，比如index__1。最后，index__1将有一个潜在ans的结束索引。

3-从begin遍历数组到index__1，递减元素计数。停止，每当元素计数从1变为0时，在一个变量中记录它的索引，比如index_1_0。子数组Aindex_1_0 : index__1是一个潜在的ans，记录下来。

4-从index__1向end遍历，增加元素计数，并在找到元素Aindex_1_时停止。使用当前索引更新index__1。

5-从index_1_0+1遍历到index__1，递减元素计数。只要元素计数从1更改为0，就会停止。这是新的index_1_0。如果子数组Aindex_1_0: index__1比前面的ans小，请更新它并继续执行步骤4和步骤5，直到遍历完整个数组。