Array: 1 2 5 8 7 6 2 6 5 3 8 5
Numbers: 5 7
那么最短的子数组显然是 Array[2:5] （Python 表示法）。
此外，如果出于某种原因（例如在线算法），您想避免对数组进行排序，您会怎么做？
我会使用右扩展表示将范围的右端点增加1，左收缩表示将范围的左端点增加1。这个答案是Aasmund Eldhuset's answer的一个小变化。区别在于，一旦我们找到最小的j使得[0，j]包含所有感兴趣的数字，我们之后就只考虑包含所有感兴趣的数字的范围。（可能会这样理解Aasmund的答案，但也可能将其解释为允许由于左收缩而丢失单个有趣数字）。
基本思想是，对于每个位置j，我们将找到以位置j结束的满足要求的最短范围，假设我们已经知道了以位置j-1 结束的满足要求的最短范围。
编辑: 修正了基础案例中的错误。
基础案例: 找到最小的j'，使得[0，j']包含所有有趣的数字。根据构造，不能存在包含所有有趣的数字的[0，k < j']范围，所以我们不需要进一步考虑它们。现在找到最小最大的i，使得[i，j']包含所有有趣的数字（即保持j'固定）。这是以位置j'结束的最小满足要求的范围。
为了找到以任意位置j结束的最小满足要求的范围，我们可以将以位置j-1 结束的最小满足要求的范围向右扩展1个位置。这个范围必然也包含所有有趣的数字，但可能不是最短的长度。我们已经知道这是一个满足要求的范围，意味着我们不必担心向左“反向”延伸范围，因为那只会增加范围超过其最小长度（即使解决方案更糟）。我们需要考虑的唯一操作是保持包含所有有趣数字属性的左收缩。因此，在满足此属性的情况下尽可能推进范围的左端点。当无法再进行左收缩时，我们就找到了以j结束的最小满足要求的范围（因为进一步的左收缩显然不能再使范围满足要求），这时我们就完成了。
由于我们在每个最右端的位置j上执行此操作，因此可以在所有最右端的位置中取最小长度范围，以找到整体最小值。这可以使用嵌套循环来完成，在每个外部循环周期中，j都会向前推进1次。显然，j会向前推进1 n次。由于在任何时候，我们只需要知道以前一个j值为最佳范围的最左侧位置，因此我们可以将其存储在i中，并根据需要进行更新。 i始终从0开始，始终<= j <= n，仅向上方向上升，最多可以向上升n次。i和j都最多向前推进n次，因此该算法具有线性时间复杂度。
下面是伪代码，将两个阶段合并为单
# x[0..m-1] is the array of interesting numbers.
# Load them into a hash/dictionary:
For i from 0 to m-1:
isInteresting[x[i]] = 1
i = 0
nDistinctInteresting = 0
minRange = infinity
For j from 0 to n-1:
If count[a[j]] == 0 and isInteresting[a[j]]:
nDistinctInteresting++
count[a[j]]++
If nDistinctInteresting == m:
# We are in phase 2: contract the left side as far as possible
While count[a[i]] > 1 or not isInteresting[a[i]]:
count[a[i]]--
i++
If j - i < minRange:
(minI, minJ) = (i, j)
count[] 和 isInteresting[] 是哈希/字典（如果涉及的数字较小，则为普通数组）。
isInteresting []是一个哈希表或字典，因此查找的时间复杂度为O(1)。我的代码目前没有显示它被填充 - 我会立即修复它。这一步将花费O(m)的时间，而m < n（否则肯定没有解决方案），因此整个过程的时间复杂度为O(n)。 - j_random_hacker这个解决方案绝对不是像上面的伪代码所建议的那样在O(n)时间内运行，然而它是一个真正的（Python）代码，可以解决问题，并根据我的估计以O(n^2)的时间运行：
def small_sub(A, B):
len_A = len(A)
len_B = len(B)
sub_A = []
sub_size = -1
dict_b = {}
for elem in B:
if elem in dict_b:
dict_b[elem] += 1
else:
dict_b.update({elem: 1})
for i in range(0, len_A - len_B + 1):
if A[i] in dict_b:
temp_size, temp_sub = find_sub(A[i:], dict_b.copy())
if (sub_size == -1 or (temp_size != -1 and temp_size < sub_size)):
sub_A = temp_sub
sub_size = temp_size
return sub_size, sub_A
def find_sub(A, dict_b):
index = 0
for i in A:
if len(dict_b) == 0:
break
if i in dict_b:
dict_b[i] -= 1
if dict_b[i] <= 0:
del(dict_b[i])
index += 1
if len(dict_b) > 0:
return -1, {}
else:
return index, A[0:index]
以下是我如何使用collections.Counter对象在线性时间内解决这个问题的方法。
from collections import Counter
def smallest_subsequence(stream, search):
if not search:
return [] # the shortest subsequence containing nothing is nothing
stream_counts = Counter(stream)
search_counts = Counter(search)
minimal_subsequence = None
start = 0
end = 0
subsequence_counts = Counter()
while True:
# while subsequence_counts doesn't have enough elements to cancel out every
# element in search_counts, take the next element from search
while search_counts - subsequence_counts:
if end == len(stream): # if we've reached the end of the list, we're done
return minimal_subsequence
subsequence_counts[stream[end]] += 1
end += 1
# while subsequence_counts has enough elements to cover search_counts, keep
# removing from the start of the sequence
while not search_counts - subsequence_counts:
if minimal_subsequence is None or (end - start) < len(minimal_subsequence):
minimal_subsequence = stream[start:end]
subsequence_counts[stream[start]] -= 1
start += 1
print(smallest_subsequence([1, 2, 5, 8, 7, 6, 2, 6, 5, 3, 8, 5], [5, 7]))
# [5, 8, 7]
假设数组有n个元素，集合有m个元素
Sort the array, noting the reverse index (position in the original array)
// O (n log n) time
for each element in given set
find it in the array
// O (m log n) time - log n for binary serch, m times
keep track of the minimum and maximum index for each found element
min - max 定义了你的范围
总时间复杂度：O((m+n)logn)
List<String> paragraph = Arrays.asList("a", "c", "d", "m", "b", "a");
Set<String> keywords = Arrays.asList("a","b");
Subarray result = new Subarray(-1,-1);
Map<String, Integer> keyWordFreq = new HashMap<>();
int numKeywords = keywords.size();
// slide the window to contain the all the keywords**
// starting with [0,0]
for (int left = 0, right = 0 ; right < paragraph.size() ; right++){
// expand right to contain all the keywords
String currRight = paragraph.get(right);
if (keywords.contains(currRight)){
keyWordFreq.put(currRight, keyWordFreq.get(currRight) == null ? 1 : keyWordFreq.get(currRight) + 1);
}
// loop enters when all the keywords are present in the current window
// contract left until the all the keywords are still present
while (keyWordFreq.size() == numKeywords){
String currLeft = paragraph.get(left);
if (keywords.contains(currLeft)){
// remove from the map if its the last available so that loop exists
if (keyWordFreq.get(currLeft).equals(1)){
// now check if current sub array is the smallest
if((result.start == -1 && result.end == -1) || (right - left) < (result.end - result.start)){
result = new Subarray(left, right);
}
keyWordFreq.remove(currLeft);
}else {
// else reduce the frequcency
keyWordFreq.put(currLeft, keyWordFreq.get(currLeft) - 1);
}
}
left++;
}
}
return result;
}