U:{A,B,C,D,E}
重复是被允许的。
例子：
S = {E,B,D,C,A,D,A,E,E,D,B,B,A,C}
问题是：
在任何给定的数组S中，我如何确定包含集合U所有元素的最短范围/路径的最有效方法？请注意，该数组无法排序。
在上面的例子中，最短路径是连接数组S的前5个元素。
编辑：
1）集合U的元素数量不是恒定的。
提前感谢您。
有趣的作业，但你仍然需要自己编码。
好消息是你没有告诉我们你使用哪种语言，所以我认为这是一个信号，表明你已经决定自己编码，这很好。
我的最佳尝试：
为子字符串（范围）有2个指针，一个指向范围的开始（较小的索引），另一个指向结束（较大的索引）。两者首先都指向数组的开头。
为范围内每个ABCDE分别设置一个列表，记录它们出现的次数。
从左到右迭代end。
对于每个字符，将列表中该字符的计数器加1。如果结果（增加的how many）> 1，看看start是否指向相同的字符。如果是，将start向前移动并减1，同时当start指向与之相关的数字> 1的字符时，继续将start向前移动并减1。
如果列表中的ABCDE都>= 1，则我们找到了一个候选范围。将其与最短长度（如果有的话）进行比较，如果更小，则更新最短长度并记录新最短范围的开始索引。
如果我理解问题正确的话，我认为你需要做的是（与语言无关）
int partLen <- U.length;
do {
Vector subSets <- S.partition(partLen);
foreach set I in subSets
if I.isEqualTo(U) then
return true;
else
partLen <- partLen + 1;
} while (partLen <= S.length);
return false;
partition 会将 S 分成任意长度的子集，isEqualTo 可以正确比较这些集合。
//Cell 0 is the last index at which we saw an A, cell 1 " " saw a B, etc.
int[] mostRecent = new int[U.length];
mostRecent.setAllValsTo(POSITIVE_INFINITY);
int shortestRange = POSITIVE_INFINITY; //We are trying to minimize this number.
int minIndex = 0; //The beginning index of the range
int maxIndex = POSITIVE_INFINITY; //The ending index of the range.
for(int i=0; i< S.length; i++) {
int currentValue = S[i]; //This value will be 0-4, corresponding to A-E
mostRecent[currentValue] = i;
currentMax = mostRecent.findMax(); //beginning of current range
currentMin = mostRecent.findMin(); //end of current range
currentRange = currentMax - currentMin;
if(currentRange < shortestRange) {
shortestRange = currentRage;
minIndex = currentMin;
maxIndex = currentMax;
}
}
//currentMax and currentMin now carry the starting and ending indices, use them as you see fit.
return shortestRange;
这是O(nk)级别的算法，其中n=S.length，k=U.length。还有很多优化空间可以挖掘，但我不知道能否将最坏情况的时间复杂度降低。
首先在数组中找到不同的元素，这是O(n)的操作。然后使用滑动窗口方法来找到包含所有这些元素的最小跨度。
您可以在这里看到如何找到最小窗口：http://tech-queries.blogspot.com/2010/12/finding-minimum-window-in-array-which.html
以下是我会如何做（伪代码）：
let counters[] be an array such that
counters[j] = number of occurrences of character j,
where j = 0 for 'A', j = 1 for 'B', etc.
build counters[] by scanning the original string s
let positions[j][] be an array listing the positions occupied by
character j in the original string s; note the size of
positions[j][] is equal to counters[j]
build positions[j][] by scanning the original string s;
let currentPositions[] be an array such that
positions[j][currentPositions[j]] gives the position of the next
occurrence of character j in the original string s
initially currentPositions[j] = 0 for every j = [0 .. u.length]
let bestLength = s.length
let bestMin = 0
let bestMax = 0
for i in [0 .. s.length] {
for j in [0 .. u.length] {
if (
positions[i][currentPositions[i]] < i and
currentPositions[j] + 1 < counters[j]
)
currentPositions[j]++
}
let min = s.length
int max = 0
for j in [0 .. u.length] {
curPos = positions[j][currentPositions[j]
if (curPos > max) let max = curPos
if (curPos < min) let min = curPos
}
if (max - min + 1 < bestLength) {
let bestMin = min
let bestMax = max
let bestLength = max - min + 1
}
}
the shortest path is that starting at bestMin, ending at bestMax,
and having length bestLength
复杂度为O(nk)，其中n = s.length，k = u.length