给定一个数组 A,找到一个最短的子数组 A[i : j ],这样 A 中存在的每个不同值也存在于子数组中。
问题不是家庭作业。这是哈希表一章中的一个练习题。我不是在找代码。只是寻找算法或提示。
1-维护哈希表元素>计数
2-从头到尾遍历数组,增加元素计数。每当元素计数从 0 更改为 1 时,将其索引记录在变量中,例如index_0_1。最后index_0_1将有一个潜在的结束索引。
3-从开始到index_0_1遍历数组,减少元素计数。停止,每当元素计数从 1 更改为 0 时,将其索引记录在变量中,例如index_1_0。子阵列 A[index_1_0 : index_0_1] 是一个潜在的 ans,请记录下来。
4-从index_0_1遍历到终点,增加元素计数,并在找到元素A[index_1_0]时停止。使用当前索引更新index_0_1。
5-从index_1_0+1遍历到index_0_1,减少元素计数。每当元素计数从 1 更改为 0 时,就停止。这是新的index_1_0。如果子阵列 A[index_1_0: index_0_1] 比以前的 ans 小,请更新它并继续执行步骤 4 和步骤 5,直到遍历整个数组。
使用哈希表来维护字符串中每种类型元素的计数。
当您找到新类型的元素时丢弃所有以前的答案并开始修剪子字符串的开头,当您可以在没有一种类型元素为零的情况下不再修剪它时记住子字符串,如果它是最短的,然后开始寻找另一个元素来替换你即将丢失的元素或找到以前未看到的新元素,如上所述。
当你点击字符串的末尾时,你就完成了。
如果你的哈希值很好,这应该是 O(n(