滑动窗口的基本思想:
-
初始化窗口:设置两个指针,通常是
left
和right
,它们表示窗口的左右边界。起初,窗口可以是一个空窗口或者包含一部分元素。 -
扩展窗口:通过移动
right
指针,扩展窗口的范围,使其包含更多的元素。 -
收缩窗口:当窗口中的元素不满足某个条件时(例如元素数量超过一定值,或者元素的某些属性不满足要求),就移动
left
指针,缩小窗口的范围。 -
更新结果:每次当窗口符合条件时,更新结果或记录窗口的位置。
This is the multi-page printable view of this section. Click here to print.
给定两个字符串 s
和 p
,找到 s
中所有 p
的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
中等
第一次尝试, 想到了滑动窗口 对目标字符串排序, 排成有序字符数组 然后在窗口截取子串, 再把子串排序 匹配, 返回窗口左边界
想法很简单, 但是这里有两个问题
每一个子串都要排序, 复杂度是
这和滑动窗口的理念不符, 滑动窗口是动态确定包含的元素的, 这种方法和迭代没区别
第二次尝试, 改进滑动窗口