例如，最初我們有一個字串abghjsag，答案應該是 6( abghjs) 我寫了一個適用于 O(n^2) 的演算法，但不知道是否有適用于 o(n) 并且可以的解決方案在谷歌找不到任何東西這是我的解決方案：
def Subbaray(s):
alphabet = set(s)
substr = []
for i in range(len(s)):
for j in range(i,len(s)):
substr.append((s[i:j 1],i,j 1))
minlen = len(s)
mini = 0
minj = len(s)-1
for subst in substr:
if len(set(subst[0])) == len(alphabet):
if len(subst[0]) < minlen:
minlen = len(subst[0])
mini = subst[1]
minj = subst[2]
return mini,minj
uj5u.com熱心網友回復：
你可以這樣做：
def get_subset(string):
return ''.join(set(string))
及其<= O(n)，輸出：
jbhgsa
uj5u.com熱心網友回復：
嘗試這樣的事情：
借助表示符號出現在 substring中的次數的陣列f，
您可以使用以下程序檢查 substring 是否有資格作為潛在答案（由出現在 中的所有符號組成）：f[i][c]cs[:i]s[i:j]s
c對于中的每個符號all symbols：檢查所有符號是否f[i][c] - f[j][c]大于或等于 1（即，每個符號在子字串中至少出現一次）
然后，使用兩個指標演算法：
j = 0
for i in range(len(s)):
while not check(i, j):
j = 1
update answer with substring s[i:j]
檢查函式將被呼叫 O(n) 次，i并且j只會通過 [0, len(s)) 一次。
校驗函式的時間復雜度為O(m)，其中m表示符號個數，初始化陣列f為O(n*m)
總時間復雜度為 O(n*m)。（但 m 真的很小，所以它本質上只是 O(n)）
uj5u.com熱心網友回復：
創建一個以字符為鍵，位置索引為值的字典，然后找到并回傳具有最小差異的索引對：
from collections import defaultdict
def min_sub(s):
chars = defaultdict(list)
for i, ch in enumerate(s):
chars[ch].append(i)
if len(chars[ch]) == 3: #remove one
if chars[ch][1] - chars[ch][0] < chars[ch][2] - chars[ch][1]:
chars[ch].pop()
else:
chars[ch].pop(0)
min_idxs = []
min_len = len(s) 1
for idxs in chars.values():
if len(idxs) != 2:
continue
new_len = idxs[1]-idxs[0]
if new_len < min_len:
min_len = new_len
min_idxs = idxs
return min_idxs
min_sub('abghjsag')
[2, 7]
min_sub('abghjsaga')
[6, 8]
min_sub('abghjsagaa')
[8, 9]
min_sub('abcd')
[]
（旁注：您的示例中的最小子字串是從g到g，而不是從a到a）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505886.html