寻找包含数组/向量所有元素的最小子数组长度的算法

Question

假设我们有一个数组 {7， 3， 7， 3， 1， 3， 4， 1}。我需要的是一个算法（最好是一些 C 代码示例），它将返回包含数组所有元素的最小子数组的长度。

在这种情况下，它将是 5：{7， 3， 1， 3， 4}，这是原始数组的最短子数组，其中包含数组的所有元素，即 1、3、4 和 7。

此外，数组 {2， 1， 1， 3， 2， 1， 1， 3} 的另一个示例，算法应返回 3，因为我们正在寻找的子数组是 {1， 3， 2}（原始数组的索引 2-4）。

我在这里发现了一些类似的问题：找到包含列表所有元素的子列表的最小长度，但似乎没有答案。

函数签名应该是：＜code＞int算法（std:：vector

Answer 1

在O(n)中查找最后一个子数组:

例如，对于数组< code>[1，2，3，2，2，1，1]，获取哈希表/映射(或小范围数组)中项的计数:< code>{ 1: 3，2: 3，3: 1 }

要查找子数组的起始索引，请从数组中的第一个值开始，并检查其计数是否大于 1。如果它的计数大于 1，则将其计数减少 1，然后继续下一个值，直到计数的值为 1。向后重复相同的操作以找到子数组的最后一个索引：

1, 2, 3, 2, 2, 1, 1
      ^        ^

在O(n)中找到其余的子数组:

现在要检查这是否是最小的子阵列，请检查它之前的子阵列。为此，在第一个索引之前搜索位于最后一个索引的值1的最后一个。如果找到，请将第一个索引更改为它，并将最后一个索引减少一：

1, 2, 3, 2, 2, 1, 1
^           ^

现在要查找新子数组的最后一个索引，请在第一个索引和最后一个索引之间搜索位于最后一个索引处的值2并将最后一个索引更改为它：

1, 2, 3, 2, 2, 1, 1
^        ^  

重复，直到在第一个和最后一个索引之间找不到最后一个索引处的值:

1, 2, 3, 2, 2, 1, 1
^     ^  

现在检查新子数组的计数是否小于先前子数组的计数，并根据需要更新当前最小子数组的索引。

必须重复搜索其余子数组，直到在第一个索引之前找不到最后一个索引的值。