查找数组中包含数组中存在的所有元素的最短范围

Question

考虑一个数组A []，其中可以包含非独立整数，我如何才能找到涵盖数组中存在的所有元素的最短范围？在范围[3,7]

A[] = 7 3 1 7 3 1 3 4 1 
index= 0 1 2 3 4 5 6 7 8 

元件形成存在于阵列中的最短范围。
因此，答案必须是5.
如何使用双指针解决此问题？
P.S.：这个问题是而不是来自任何现场比赛。
我的尝试：我采取了一个变量len，我将从1到数组长度不等，每个len检查它是否覆盖所有元素。

Answer 1

让我们的数组长度为N，不同元素的数量为K,K<=N。 我们假设值为0,1，...，K-1。

（我们可以为所有元素排序，然后用0替换最小值元素，与1秒最小值等元素，然后把它们回到原来的位置。它需要O(N*log(N)复杂性。）制造阵列C[K]，其中C[i]应在段[x, y]中保留值为i的元素的计数。 让D是一个段中的多个不同元素。

如果我们通过增加y来扩展此类细分市场，我们会将C[A[y+1]]增加1。 如果C[A[y+1]]变成1，我们将D增加1。

如果我们通过增加x来缩小细分市场，我们会将C[A[x+1]]减1。 如果C[A[x+1]]变成0，我们将D减少1。

因此，如果D==K我们知道该段包含所有元素。

现在从[0, 0]开始，并继续扩展段，直到它包含所有可能的值。它是[0, q]。 然后缩小它，同时生成的段仍具有包含所有可能值的元素。让它成为[p, q]。

将[p, q]右移一位，即[p+1, q+1]。 再次尝试缩小分段。等

因此，粗略地说，从左到右移动段，并尝试在每一步缩小它。当你到达最后，不能再移动左端时，你就完成了。它是O(N)。所以一起（包括分拣）：O(N*log(N))。