查找查找所有唯一路径的“最短索引范围”的大小被传递

Question

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

例如，A = { E, R, E, R, A, R, T, A }，应该是5。正如我们所看到的，A[2] = E and 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包含所有唯一的路径。(C、A、R)
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元素的当前字符增量计数器。当dict大小(在非零元素数组数的情况下)等于unique时，停止

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

继续进行R等等

在扫描过程中选择最短的间隔。

类似问题here的Python代码

Answer 2

我将把“所有唯一的道路”解释为“所有可能的价值”。

对于具有n唯一值的长度字符串，可以使用字典和优先级队列在时间O(n log(k))中求解。主要的想法是：

1. 第一次，找到所有可能的值。
2. 第二次，保存一个字典most_recently_found，说明最近找到每个值的位置。
3. 保持一个优先级队列longest_since，其值是自找到它以来最长的。
4. 保持最短距离的最小跑步距离。

现在，当您返回并找到所有值时，您将遵循如下所示的每个迭代逻辑：

most_recently_found[current_value] = current_position
oldest = longest_since.top()
if current_value == oldest.value:
    while oldest.position() != most_recently_found[oldest.position()]:
        longest_since.pop()
        longest_since.push({value: top.value, position: most_recently_found[oldest.position()]
        oldest = longest_since.top()
if current_position - oldest.position() < best_gap:
    best_gap = current_position - oldest.position()

要点是，对于找到的每个值，您必须更新字典(O(1))，可能必须将其从优先级队列(O(k))中删除，可能必须在优先级队列(O(k))上添加一些新的内容，并且可能需要执行一些算术(O(1))。因此，O(n log(k))适用于一切。