本文记录作者刷题过程中与滑动窗口相关的题目。
1、连续子数组
674. 最长连续递增序列（简单难度）
子数组是原数组中连续的元素，中间不可以删除或添加其他元素，每个元素的相对顺序和原数组相同
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int len=nums.size();
if(len==1) return 1;
int res=0;// 最长长度
int left=0;
int right=1;
// 滑动窗口[left,right)表示递增区间，负责搜索数组中的所有递增区间
while(right<len){
// 如果新元素递增，扩展右边界
if(nums[right-1]<nums[right]){
right++;
}
// 如果新元素非递增，更新左边界，扩展右边界
else{
left=right;
right++;
}
res=max(res,right-left);//不断更新递增区间的最大长度
}
return res;
}
};
剑指 Offer 57 - II. 和为s的连续正数序列（简单难度）
class Solution {
public:
/*解析：本题是从正整数序列中查找所有和为target的连续子序列
难点在于每个连续子序列的长度、数量是不确定的。
这种类型题，特别是元素都是正整数，特别适合滑动窗口算法。
请注意，左指针和右指针的移动时机
当区间和>=target,右移左指针；当区间和<target，右移右指针
进阶：求解区间和的数学技巧：(left+right)*(right-left+1)/2
*/
vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>> res;
int left=1;//正整数序列的第1个数
int right=2;//正整数序列的第2个数
int sum=0;
vector<int> sub;
// 滑动窗口[left,right]
while(left<right){
// 计算滑动窗口[left,right]的和
sum=0;
sub.clear();
for(int i=left;i<=right;i++){
sum+=i;
sub.push_back(i);
}
// 如果区间和==target，移动左指针
if(sum==target) {
res.push_back(sub);
left++;
}
// 如果区间和<target,右指针右移
else if(sum<target) right++;
// 如果区间和>target,左指针右移
else left++;
}
return res;
}
};
添加数学公式优化后：
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>> res;
int left=1;//正整数序列的第1个数
int right=2;//正整数序列的第2个数
int sum=0;
vector<int> sub;
// 滑动窗口[left,right]
while(left<right){
// 计算滑动窗口[left,right]的和
sum=(left+right)*(right-left+1)/2;
// 如果区间和==target，移动左指针
if(sum==target) {
sub.clear();
for(int i=left;i<=right;i++){
sub.push_back(i);
}
res.push_back(sub);
left++;
}
// 如果区间和<target,右指针右移
else if(sum<target) right++;
// 如果区间和>target,左指针右移
else left++;
}
return res;
}
};
209. 长度最小的子数组
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int minLength = INT32_MAX; // 求最小值就以整数的较大值初始化
int curlength = 0;//当前值
int start=0;//滑动窗口起始位置
int end=0;//滑动窗口终止位置
int sum=0;
//不满足滑动条件时就不断移动终止位置
for(int end=0;end<nums.size();end++){
sum+=nums[end];
//当满足条件时就不断移动起始位置
while(sum>=target){
curlength = end-start+1;//计算当前滑动窗口代表的值
minLength = minLength < curlength ? minLength : curlength;//注意：当前最小不一定就是全局最小
sum-=nums[start++];//滑动窗口起始位置后移
}
}
return minLength == INT32_MAX ? 0 : minLength;
}
};
904. 水果成篮
class Solution {
public:
int totalFruit1(vector<int>& tree) {
vector<int> count(tree.size());
int start = 0;//滑动窗口起始位置
int end =0;//滑动窗口终止位置
int dif = 0;//水果种类
for(end = 0; end < tree.size(); end++) {
if(count[tree[end]] == 0) {
count[tree[end]]++;//该种类水果数量+1
dif++;//种类+1
}
if(dif > 2) {
count[tree[start]]--;
if(count[tree[start]] == 0) {
//start++;
dif--;
}
start++;
}
}
return end - start;
}
/*这道题目可以理解为求只包含两种元素的最长连续子序列*/
int totalFruit(vector<int>& tree) {
int K = 2;
int end = 0, start = 0, res = 0;
unordered_map<int, int> dict;
for (end = 0; end < tree.size(); end++) {
dict[tree[end]]++;//该种类水果数量增加
//当不符合滑动窗口条件时
while(dict.size() > K)
{
res = max(res, end - start);
dict[tree[start]]--;
if(dict[tree[start]] == 0) {
dict.erase(tree[start]);
}
start++;
}
}
res = max(res, end - start);
return res;
}
};
3. 无重复字符的最长子串
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> dict;// <字符，频率>
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int right=-1;
int res=0;
// 枚举左指针的位置，初始值隐性地表示为 -1
for(int left=0;left<s.length();++left){
if(left!=0) dict.erase(s[left-1]);
// 当右指针下一步没有到达数组右边界且右指针下一步没有重复，不断地移动右指针
while(right+1<s.length()&&!dict.count(s[right+1])){
dict[s[right+1]]++;
right++;
}
// 第 left 到 right 个字符是一个最长的无重复字符子串
res = max(res, right - left + 1);
}
return res;
}
};
567. 字符串的排列
剑指 Offer II 014. 字符串中的变位词
class Solution {
public:
/*由于排列不会改变字符串中每个字符的个数，
所以只有当两个字符串每个字符的个数均相等时，
一个字符串才是另一个字符串的排列。
记 s1的长度为n，我们可以遍历2中的每个长度为n 的子串，
判断子串和s1中每个字符的个数是否相等，
若相等则说明该子串是s1的一个排列*/
bool checkInclusion(string s1, string s2) {
int n = s1.length(), m = s2.length();
if (n > m) return false;
vector<int> cnt1(26), cnt2(26);
for (int i = 0; i<n; ++i) {
++cnt1[s1[i]-'a'];
++cnt2[s2[i]-'a'];
}
if (cnt1 == cnt2) return true;
for (int i = n; i < m; ++i) {
++cnt2[s2[i]-'a'];
--cnt2[s2[i -n]-'a'];
if (cnt1 == cnt2) return true;
}
return false;
}
};
438. 找到字符串中所有字母异位词
class Solution {
public:
/**时间复杂度O(N)，空间复杂度O(1)； 技术：滑动窗口+计数索引
一、计数索引，两个串中的字母只有小写英文字母，用大小为26的数组存放字母频率
二、滑动窗口[left,right]
在s中移动一个滑动窗口，如果滑动窗口内的字母频率>=t的字母频率,则滑动窗口符合条件
移动滑动窗口时，需要时刻维护滑动窗口内的所有字母频率sFreq
left的移动范围是[0,s_len-t_len],right的移动范围是[-1,s_len-1]
如何移动滑动窗口呢？默认先移动right，比较winSize和t.size()，判断是否移动left：
1) 当winSize < t.size() 移动right;// 此时滑动窗口一定不符合要求
2) 当winSize == t.size() 并且符合要求时: 添加left到结果中，移动left
3) 当不符合要求时: 移动left*/
vector<int> findAnagrams(string s, string p) {
vector<int> res;
int s_len=s.length();
int p_len=p.length();
if(s_len<p_len) return res;
// 统计p的字母频率
vector<int> pFec(26,0);
for(char c:p) pFec[c-'a']++;
// 滑动窗口
int left=0;// 遍历范围为[0,s_len-p_len]
int right=-1;// 遍历范围为[-1,s_len-1]
vector<int> winFec(26,0);
while(left<=s_len-p_len){
int winSize=right-left+1;
// 如果滑动窗口尺寸较小，移动right
if(winSize<p_len){
right++;
winFec[s[right]-'a']++;
}
// 如果滑动窗口尺寸正好，检查要求,移动left缩小
else if(winSize==p_len&&check(winFec,pFec)){
res.push_back(left); // 符合条件
winFec[s[left++]-'a']--; // 缩小窗口
}
// 如果滑动窗口尺寸较大,移动left缩小
else winFec[s[left++]-'a']--; // 缩小窗口
}
return res;
}
bool check(vector<int>& sFec,vector<int>& pFec){
for(int i=0;i<26;++i) if(sFec[i]!=pFec[i]) return false;
return true;
}
};
76. 最小覆盖子串
class Solution {
public:
/**时间复杂度O(N)，空间复杂度O(1)； 技术：滑动窗口+计数索引
一、计数索引
该题目的两个串中的字母只有大小写英文字母，可以开辟一个大小为64的数组存放字母频率
通过字母的ASCII码作为数组的索引，开辟空间的大小为26+6+26=58：26个大写字母，26个小写字母，
还有中间的6个非字母 A~Z[65~90] 非字母[91~96] a~z[97~122]
二、滑动窗口[left,right]
在s中移动一个滑动窗口，如果滑动窗口内的字母频率>=t的字母频率,则滑动窗口符合条件
移动滑动窗口时，需要时刻维护滑动窗口内的所有字母频率sFreq
left的移动范围是[0,s_len-t_len],right的移动范围是[-1,s_len-1]
如何移动滑动窗口呢？默认先移动right，比较winSize和t.size()，判断是否移动left：
1) 当winSize < t.size() 移动right;// 此时滑动窗口一定不符合要求
2) 当winSize >= t.size() :
2.1) 如果滑动窗口符合要求：
2.1.1）winSize == t.size()时，一定是最小覆盖子串，直接return
2.1.2) winSize > t.size()时，保存left和right,尝试移动left
2.2) 如果滑动窗口不符合要求：
2.2.1）如果right移动到头，移动left
2.2.2) 如果right没有移动到头，移动right
*/
string minWindow(string s, string t) {
int t_len=t.size();
int s_len=s.size();
if (s_len<t_len) return "";
// 统计t字符串中每个字母的出现频率
vector<int> tFreq(64,0);// t字母串的所有字母频率
for (int i=0; i<t_len; i++) tFreq[t[i]-'A']++;
// 滑动窗口为[left,right]，窗口大小是winSize=right-left+1
int left = 0, right = -1;
vector<int> winFreq(64,0);// 滑动窗口的所有字母频率
int edge[2]={-1,s_len+1}; // 保存的最小覆盖子串的左右边界
while (left <= s_len-t_len) {
int winSize=right-left+1;
//窗口较小时，移动right
if(winSize<t_len) {
//if (right+1>=s_len) break;// 防止越界
right++;//移动右边界
winFreq[s[right]-'A']++;
}
// 如果符合要求
else if(check(winFreq,tFreq)){
// 如果窗口大小==t的长度，一定是最小覆盖子串
if (winSize == t.size()) return string(s.begin()+left, s.begin()+right+1);
// 如果窗口大小>t的长度，不一定是最小覆盖子串，可能要保存，移动left
else {
// 如果比上个保存子串小，则更新
if (right-left<edge[1]-edge[0]) {
edge[0] = left;
edge[1] = right;
}
winFreq[s[left]-'A']--;
left++;
}
}
// 如果不符合要求，移动right
else{
// 如果right没有越界，移动right
if (right+1<s_len) {
right++;
winFreq[s[right]-'A']++;
}
// 如果right已经到头，移动left
else{
winFreq[s[left]-'A']--;
left++;
}
}
}
return edge[0] == -1 ? "" : string(s.begin() + edge[0], s.begin() + edge[1] + 1);
}
// 检查此时窗口中的字母频率是否和t的频率一致
bool check(vector<int>& winFreq, vector<int>& tFreq){
for(int i = 0;i < 64;i++){
if (winFreq[i]<tFreq[i]) return false;
}
return true;
}
};