java - 使用散列法查找总长度最小的字符串子数组，该子数组包含原始数组中的所有不同字符串

Question

大家好，这是一个关于散列的 Java 练习。首先我们有一个包含 N 个字符串的数组 (1<=N<=100000)，程序将找到包含原始数组中所有不同字符串的连续子序列的最小长度。

例如原数组为{apple,orange,orange pear,pear apple,pear}

连续的子数组可以是{orange, pear, pear, apple}

所以答案是19

我编写了一段代码，它访问数组中的每个元素并创建一个新的哈希表来查找包含所有不同字符串的子数组的长度。一旦 N 大于 1000，它就会变得非常非常慢。所以我希望有一个更快的算法。谢谢!

Answer 1

1. 遍历数组一次，使用散列来跟踪您之前是否看过某个单词。仅当您第一次看到一个词时，通过添加计数来计算数组中不同的词。

2. 第二次遍历数组，使用散列来跟踪您看到每个单词的次数。还要跟踪您看到的所有单词的长度总和。继续前进，直到您至少看过所有单词一次。

3. 现在，在不将单词计数减少到零的情况下尽可能向前移动范围的开头。请记住相应地调整您的散列和字母数。这为您提供了第一个范围，其中每个单词至少包含一次，并且在不排除单词的情况下无法减少。

4. 重复执行以下操作:将范围的左端向前移动一个，然后将右端向前移动，直到找到刚刚从左端启动的单词的另一个实例。每次执行此操作时，您都会有另一个最小范围，其中包含每个单词一次。

在执行第 3 步和第 4 步时，跟踪到目前为止的最小长度，以及相关范围的开始和结束。当您需要将范围的右端移动到数组末尾之后时，您就完成了。此时，您拥有正确的最小长度，以及实现它的范围。

这在线性时间内运行。