查找包含 array/vector 的所有元素的最小子数组长度的算法

Question

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

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

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

我在这里发现了一些类似的问题：Find minimum length of sub-list containing all elements of a list 但似乎没有回答。

函数签名应该是这样的： int algorithm(std::vector<int> &arr){...}

Answer 1

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

例如，对于数组 [1, 2, 3, 2, 2, 1, 1]，获取散列 table/Map（或小范围数组）中项目的计数：{ 1: 3, 2: 3, 3: 1 }

要找到子数组的起始索引，从数组中的第一个值开始，检查它的计数是否大于1。如果它的计数大于1，则将其计数减一，并继续下一步value 直到计数为 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
^     ^

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

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

Algorithm to find length of a minimal sub-array containing all the elements of an array/vector