滑动窗口算法

参考文章：leetcode438 题解答

0x00：前言

leetcode 上有好几道个子字符串有关的题目，两天前看到一题要求找到字符串中所有字母异位词，题目大致意思是有 s 和 p 两个字符串，找出 s 中和 p 字母相同但顺序可以不相同的子字符串，并返回这些子串的起始索引。

例子：
输入:
s: “cbaebabacd” p: “abc”
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。
题目链接：https://leetcode-cn.com/probl…

0x01：算法思路

想象一块在窗口上 滑动 的玻璃窗，它的“左”边和“右”边都是可以移动的，也就是这个玻璃窗的位置可以移动，宽度也可以变化。这么一说好像更像窗帘……

思路如下：

1. 建立双指针，初始化 left 与 right 两个指针，以 [left, right] 这个闭区间做为窗口
2. 首先拉动这个窗口的右边，窗口不断扩大，直到窗口中内容符合要求
3. 现在移动窗口的左边，直到窗口中内容不符合要求
4. 重复 2、3 步骤，直到窗口右边达到边界

使用这种方式，可以方便的解决子字符串相关问题。

0x02：具体解决

• 首先在代码中，双指针 right 和left不能少，同时还需要一个值来记录匹配情况
• 返回值需要一个列表，来记录匹配的子字符串首位索引
• 使用 hash 表来记录字符串 p 中各个字符数量，在 Python 中使用 Count 类，它是字典 dict 的子类，可以使用字典常用的方法
• 移动 right 来遍历字符串 s，如果 right 所在的字符存在于 t 中，将其存入 window 这个字典中，并将记录其数量的值加一。

window[key] = window.get(key, 0) + 1
# 字典的 get 方法：dict.get(key, default=None)，返回字典中 key 的值，如果 key 不存在，就返回默认的 default 值。# 这样写保证 window[key]值增加 1，如果不存在这个键就会创建

• 当 window 中记录字符的数量与 needs 中相等时，表示我们匹配完了一个字符，将 match 值加一
• 等到匹配的字符长度合适了，就可以将 left 的值 append 到需要返回的列表中去了

 while match == len(needs):
     if right - left == len(p):
         res.append(left)

• 移动 left，直到窗口内容不再符合我们需要的异序字符串，将match 值也减一

完整代码如下：

from collections import Counter
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []
        right, left, match = 0, 0, 0
        needs = Counter(p)
        window = {}
        
        while right < len(s):
            key1 = s[right]
            if key1 in needs:
                window[key1] = window.get(key1, 0) + 1
                if window[key1] == needs[key1]:
                    match += 1
            right += 1
            
            while match == len(needs):
                if right - left == len(p):
                    res.append(left)
                    
                key2 = s[left]
                if key2 in needs:
                    window[key2] = window[key2] - 1
                    if window[key2] < needs[key2]:
                        match -= 1
                left += 1
        return res

扫描二维码关注公众号查看更多文章：