algorithm - 查找 'shortest range of indices' 的大小，查找所有唯一路径已通过

Question

给定一个字符串数组，查找“最短索引范围”的大小，查找所有唯一路径。

例如，A = { E, R, E, R, A, R, T, A }，它应该是5。如我们所见，A[2] = E 和 A[6] = T 的范围包含所有唯一路径。 (在本例中，E、R、A、T)

我可以像下面这样用多个循环来解决。 (由 Kotlin 解决。)

fun problem(array: Array<String>): Int {
    if (array.isEmpty()) return 0
    val unique = array.distinct()
    var result = 200000
    for (i in 0 until A.size) {
        val tempSet = HashSet<String>()
        val remaining = A.sliceArray(i until array.size)
        var count = 0

        while (true) {
            tempSet.add(remaining[count])
            if (unique.size == tempSet.size) break
            count++

            if (count == remaining.size) {
                count = 200000
                break
            }
        }

        result = Math.min(result, count + 1)
    }

    return result
}

但是当一个大数组(大约100,000个)进来时，我不知道如何减少时间。我该怎么办？

一些测试用例:

1. [E, R, E, R, A, R, T, A] -> 5. 因为 [2..6] 包含所有唯一路径。 (E, R, A, T)

2. [C, A, A, R, C, A, A, R] -> 3。因为 [3..5] 包含所有唯一路径。 (三，一，右)

3. [R, T, A, R, A, R, E, R] -> 6. 因为 [1..6] 包含所有唯一路径。 (T, A, R, E)

4. [A, R, R, C, T, E, A, R] -> 5. 因为 [2..6] 包含所有唯一路径。 (R, C, T, E, A)

Answer 1

这个问题或许可以通过“两点式”的方法得到有效解决。

创建包含 char 作为键和计数器作为值的字典结构(在最简单的情况下 - int 数组)

在0中设置两个索引L和R。

右移R，对应dict元素的当前char增量计数器。当 dict 大小(在数组的情况下 - 非零元素的数量)变得等于 unique 时，停止

现在右移L，对应dict元素的当前char递减计数器，当计数器为零时移除元素。当 dict 大小变得小于 unique 时，停止。在最后一步，L..R 区间包含所有可能的项目。

继续R等

选择扫描时的最短间隔。

类似问题的 Python 代码 here