This is the multi-page printable view of this section. Click here to print.

Return to the regular view of this page.

滑动窗口

滑动窗口的基本思想：

  1. 初始化窗口：设置两个指针，通常是 left 和 right，它们表示窗口的左右边界。起初，窗口可以是一个空窗口或者包含一部分元素。

  2. 扩展窗口：通过移动 right 指针，扩展窗口的范围，使其包含更多的元素。

  3. 收缩窗口：当窗口中的元素不满足某个条件时（例如元素数量超过一定值，或者元素的某些属性不满足要求），就移动 left 指针，缩小窗口的范围。

  4. 更新结果：每次当窗口符合条件时，更新结果或记录窗口的位置。

1 - 438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

题意:

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

难度:

中等

示例:

image.png

解析:

第一次尝试, 想到了滑动窗口 对目标字符串排序, 排成有序字符数组 然后在窗口截取子串, 再把子串排序 匹配, 返回窗口左边界

image.png

想法很简单, 但是这里有两个问题

  • 每一个子串都要排序, 复杂度是 image.png

  • 这和滑动窗口的理念不符, 滑动窗口是动态确定包含的元素的, 这种方法和迭代没区别

第二次尝试, 改进滑动窗口

  • 为了减少排序的复杂度, 我们使用哈希表 + 字符频率来防止排序
  • 使用两个指针来维护定长窗口, 但是右指针是拓展指针, 左指针是收缩指针,