我目前正在准备一次技术面试,并用Python练习一些数据 struct 和算法问题.有一个常见问题要求您查找字符串中最长的子字符串,以便该子字符串不包含重复字符.凭直觉,我知道如何使用滑动窗口来解决这个问题,这可以通过以下方式实现:
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
它在线性时间内解决了这个问题.我已经分清了代码的作用,理解了各个部分,但无法将其与滑动窗口的工作方式联系起来,这使我无法将这种方法应用于不同的问题.我可以只记住代码,但我想了解第二个代码块中发生的事情与第一个代码块中发生的事情是如何相似的.有谁能用一种直截了当的方式来解释这一点,说明第二种变体是如何实现滑动窗口的?