滑动窗口基础

滑动窗口常用来解决求字符串子串问题,借助map和计数器,其能在O(n)时间复杂度求子串问题。滑动窗口和双指针(Two pointers)有些类似,可以理解为往同一个方向走的双指针。常用滑动窗口代码框架如下:

    //3. Longest Substring Without Repeating Characters
int lengthOfLongestSubstring(string s) {
vector<int> v(,); //用于对窗口内的各个字符计数
int begin=,end=,res=0; //begin,end标识窗口的头尾
int cnt=; //窗口计数器
while(end<s.length()){
if(v[s[end++]]++>) cnt++; //end++右侧窗口往右扩展
//检测到不满足条件时(如这里出现重复字符),begin++左侧窗口往右缩小
while(cnt>) if(v[s[begin++]]-->) cnt--;
res=max(res,end-begin);
}
return res;
}

以"pwwkew"为例,以上滑动窗口执行过程图示如下:

LeetCode编程训练 - 滑动窗口(Sliding Window)-LMLPHP

相关LeetCode题:

3. Longest Substring Without Repeating Characters  题解

159. Longest Substring with At Most Two Distinct Characters  题解

992. Subarrays with K Different Integers  题解

76. Minimum Window Substring  题解  讨论

1004. Max Consecutive Ones III  题解

763. Partition Labels  题解

滑动窗口内的数据还可以存入更复杂一些的数据结构中,以利用这些数据结构的特性更方便地对数据进行处理,例如以下用到deque/multiset的题目。

相关LeetCode题:

239. Sliding Window Maximum  题解

480. Sliding Window Median  题解

05-07 15:26