滑动窗口算法

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

参考文章:leetcode438题解答

0x00:前言

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

例子:
输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
题目链接:https://leetcode-cn.com/problems/find-all-anagrams-in-a-string

0x01:算法思路

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

思路如下:

  1. 建立双指针,初始化left与right两个指针,以[left, right]这个闭区间做为窗口

  2. 首先拉动这个窗口的右边,窗口不断扩大,直到窗口中内容符合要求

  3. 现在移动窗口的左边,直到窗口中内容不符合要求

  4. 重复2、3步骤,直到窗口右边达到边界

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

0x02:具体解决

  • 首先在代码中,双指针rightleft不能少,同时还需要一个值来记录匹配情况

  • 返回值需要一个列表,来记录匹配的子字符串首位索引

  • 使用hash表来记录字符串p中各个字符数量,在Python中使用Count类,它是字典dict的子类,可以使用字典常用的方法

  • 移动right来遍历字符串s,如果right所在的字符存在于t中,将其存入window这个字典中,并将记录其数量的值加一。

1window[key] = window.get(key, 0) + 1
2# 字典的get方法:dict.get(key, default=None),返回字典中key的值,如果key不存在,就返回默认的default值。
3# 这样写保证window[key]值增加1,如果不存在这个键就会创建
  • window中记录字符的数量与needs中相等时,表示我们匹配完了一个字符,将match值加一

  • 等到匹配的字符长度合适了,就可以将left的值append到需要返回的列表中去了

1 while match == len(needs):
2     if right - left == len(p):
3         res.append(left)
  • 移动left,直到窗口内容不再符合我们需要的异序字符串,将match值也减一

完整代码如下:

 1from collections import Counter
2class Solution:
3    def findAnagrams(self, s: str, p: str) -> List[int]:
4        res = []
5        right, left, match = 000
6        needs = Counter(p)
7        window = {}
8
9        while right < len(s):
10            key1 = s[right]
11            if key1 in needs:
12                window[key1] = window.get(key1, 0) + 1
13                if window[key1] == needs[key1]:
14                    match += 1
15            right += 1
16
17            while match == len(needs):
18                if right - left == len(p):
19                    res.append(left)
20
21                key2 = s[left]
22                if key2 in needs:
23                    window[key2] = window[key2] - 1
24                    if window[key2] < needs[key2]:
25                        match -= 1
26                left += 1
27        return res


关注一个呗:

滑动窗口算法


原文始发于微信公众号(公子政的宅日常):滑动窗口算法