算法现学现卖—— 滑动窗口

作者:杨润炜
日期:2020/5/2 14:52

简述

滑动窗口,高级指针编程技巧,可以用于判断数组、链表、字符串等线性结构的子结构问题。

编程过程中,用左右指针形成的区间作为窗口,对窗口中的子结构进行判断,然后扩展右指针或缩小左指针,最终遍历完整个数据,窗口也记录下所有满足条件的子结构。

代码模板

  1. left, right = 0, 0
  2. window = []
  3. while right < size:
  4. right += 1
  5. window.append(right)
  6. while valid:
  7. window.pop(0)
  8. left += 1

例题

无重复字符的最长子串

思路

  1. left,right是窗口的左右边界,分别从0开始向右移动,window记录窗口各字符的数量,res记录窗口历史最大长度;
  2. right不断移动,如果出现window中字符数量大于1,则移动left,直到该字符数量为1,更新res;
  3. 重复2,直到right遍历到字符串末尾,返回res

    代码

    1. class Solution:
    2. def lengthOfLongestSubstring(self, s: str) -> int:
    3. left, right = 0, 0
    4. res = 0
    5. window = collections.defaultdict(int)
    6. while right < len(s):
    7. rc = s[right]
    8. window[rc] += 1
    9. right += 1
    10. while window[rc] > 1:
    11. lc = s[left]
    12. window[lc] -= 1
    13. left += 1
    14. res = max(res, right - left)
    15. return res

LeetCode题目

找到字符串中所有字母异位词
最小覆盖子串

参考

滑动窗口技巧

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/108.html
邮箱:glowrypauky@gmail.com
QQ: 892413924