我目前正在準備技術面試并用 Python 練習一些資料結構和演算法問題。有一個常見問題要求您在字串中查找最長的子字串，以使該子字串不包含重復的字符。直觀地說，我了解如何使用滑動視窗來解決這個問題，可以通過以下方式完成：
def longest_substring(s: str) -> int:
longest_sub_string = 0
if len(s) == 1:
return 1
for window_size in range(len(s) 1, 0, -1):
for i in range(len(s) - window_size 1):
window = s[i:i window_size]
if not self.contains_repeats(window) and len(window) > longest_sub_string:
longest_sub_string = len(window)
return longest_sub_string
def contains_repeats(s: str = None) -> bool:
splt = list(s)
if len(list(set(splt))) < len(splt):
return True
但是，此解決方案對于需要 O(n^2) 時間的非常長的輸入字串無效。我找到了另一種滑動視窗實作：
def longest_substring(s: str) -> int:
last_idxs = {}
max_len = 0
start_idx = 0
for i in range(0, len(s)):
if s[i] in last_idxs:
start_idx = max(start_idx, last_idxs[s[i]] 1)
max_len = max(max_len, i-start_idx 1)
last_idxs[s[i]] = i
return max_len
它在線性時間內解決了這個問題。我已經分解了代碼在做什么并理解了各個部分，但無法將其與滑動視窗的作業方式聯系起來，這使我無法將這種方法應用于不同的問題。我可以只記住代碼，但我想了解第二個代碼塊中發生的事情與第一個代碼塊中發生的事情有何相似之處。任何人都可以用一種簡單的方式來解釋這一點，展示第二個變體是如何實作滑動視窗的嗎？
uj5u.com熱心網友回復：
我不會將第一個代碼稱為“滑動視窗演算法”。它似乎只是一種嘗試所有可能子字串的蠻力演算法。它可能需要與 n3 成比例的時間，因為要檢查 n2 個子字串，并且contains_repeats在最壞的情況下，應用可能需要與每個子字串的 n 成比例的時間。或者更確切地說，如果 k 是字母表中不同字符的數量，則contains_repeats可以花費與 min(n, k) 成正比的時間；因此第一個演算法可能需要最多n2 min(n, k).
第二種演算法是滑動視窗演算法。視窗從 indexstart_idx到 index i。它所花費的時間與 n 成正比，因為這兩個索引中的每一個都只能增加而不能減少，因此迭代的總數最多為 2n。演算法沒有嘗試所有可能的子字串，而是有一個大小可變的“視窗”，它從左到右“滑動”（并且永遠不會回傳）。
請注意，“滑動視窗演算法”是一個具有至少兩個不同含義的術語。除了這種字串演算法，有時也用來指代使用卷積的演算法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/464738.html