这个算法如何实现滑动窗口？

Question

我目前正在为技术面试做准备，并使用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

这个算法可以在线性时间内解决问题。我已经分析了代码并理解了各个部分，但是无法将其与滑动窗口的工作方式联系起来，这阻止了我能够将此方法应用于不同的问题。我可以仅仅记住这段代码，但我希望能够理解第二个代码块中发生的事情与第一个代码块中发生的事情类似的原因。有人可以简单地解释一下吗，以展示第二种变体如何实现滑动窗口？

- MetaMario

---

@Stef 在我看来，把这两个评论合并成一个答案可能更好，因为这可能是 OP 所询问的。 - Abhinav Mathur

@Stef 我猜第一个算法不能变成O(n^3)，因为有效的子字符串不能超过26个字符。除了不使用哈希表/集合之外，第一个算法还查看了不现实的子字符串。如果我没有错的话，可以使它线性，尽管有一个不必要的大常数。 - user1984

哦，我现在明白了，它确实是O(n^3)，因为当发现重复时，它不会跳出for循环。第一个算法太可怕了。难以阅读且效率低下 :D - user1984

第二个函数有效吗？它对于 'aabbbcccccccccccccccccgdef' 返回 5。 - wwii

@wwii 那不是正确答案吗？因为 'cgdef' 是最长的没有重复字符的子串。 - kcsquared

@kcsquared ... 我看错了 - wwii

Answer 1

我不会称第一个代码为“滑动窗口算法”。它似乎只是一个暴力算法，尝试所有可能的子字符串。它可能需要时间与n³成比例，因为有n²个子字符串要检查，并且在最坏情况下，对每个子字符串应用contains_repeats可能需要与n成比例的时间。或者更确切地说，如果k是字母表中不同字符的数量，则contains_repeats可能需要与min(n，k)成比例的时间；因此第一个算法可能需要最多n² min(n，k)的时间。

第二个算法是一种滑动窗口算法。窗口从索引start_idx到索引i。它需要时间与n成比例，因为这两个索引只能增加，永远不能减少，因此迭代的总次数最多为2n。算法没有尝试所有可能的子字符串，而是具有可变大小的“窗口”，该“窗口”从左到右“滑动”（并且永远不会返回）。

请注意，“滑动窗口算法”是一个术语，至少有两个不同的含义。除了这种字符串算法之外，它有时用于指使用卷积的算法。

- Stef