滑动窗口，水果成篮 , 找到字符串中所有字母异位词 ,串联所有单词的子串
滑动窗口
滑动窗口（Sliding Window）是一种在计算机科学中用于解决各种子数组或子字符串问题的技术。滑动窗口技术通过维护一个固定大小的窗口在数组或字符串上移动，从而使得可以在较短的时间内解决一些复杂的问题。这种方法在处理一系列数据时特别高效。滑动窗口（Sliding Window）是一种在计算机科学中用于解决各种子数组或子字符串问题的技术。滑动窗口技术通过维护一个固定大小的窗口在数组或字符串上移动，从而使得可以在较短的时间内解决一些复杂的问题。这种方法在处理一系列数据时特别高效。
滑动窗口其实可以理解为一个左指针和一个右指针共同维护的一个区间，然后一起移动，这个区间的长度可能是不变的，也可能是变化的。
滑动窗口的几个基本步骤：
- 进窗口
- 判断
- 出窗口并更新结果
接下来我们用几道题来演示滑动窗口这个算法。
1. 水果成篮
题目链接
滑动窗口的几个基本步骤：
- 进窗口条件 ： 因为题目中1 <= fruits.length <= 10^5，故建立int hash[100001] = {0}; 来标记每种树进了多少，并且需要一个count来记录hash表中有几种树
进窗口的条件和判断的条件有关（这样想不容易把进窗口条件想复杂），这里是if(hash[fruits[right]] == 0) count++; //计数++
hash[fruits[right]]++;//进窗口 - 判断 ： 题目可得当 count > 2进入循环, 说明有两种以上的树被标记，在循环里面我们要判断 出窗口条件 和 什么时候更新数据
- 出窗口并更新结果 : hash[fruits[left]]–;//出窗口
if(hash[fruits[left]] == 0) count–;//计数–
left++;； 出判断循环里面后更新结果。
class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001] = {0};//标记int left = 0, right = 0;int count = 0; //统计hash里面个数int ret = 0;while(right < fruits.size()){if(hash[fruits[right]] == 0) count++; //计数++hash[fruits[right]]++;//进窗口while(count > 2)//判断{hash[fruits[left]]--;//出窗口if(hash[fruits[left]] == 0) count--;//计数--left++;}ret = max(ret,right-left+1);//更新结果right++;}return ret;}
};
2. 找到字符串中所有字母异位词
题目链接
滑动窗口的几个基本步骤：
- 进窗口条件 ：和上一道题很相似，但是这个需要两个标记hash数组， 用 int count = 0; //s中的滑动窗口 和 p有几个字符相等
来判断 s中的滑动窗口 和 p有几个字符相等
进窗口的条件和判断的条件有关（这样想不容易把进窗口条件想复杂），这里是hash2[s[right]]++;//进窗口
if(hash2[s[right]] <= hash1[s[right]]) count++; //计数++ - 判断 ： 题目可得当 if(right - left + 1 > p.size())//判断， 这是定长滑动窗口, 说明窗口长度超过p字符串长度，里面我们要判断 出窗口条件 和 什么时候更新数据
- 出窗口并更新结果 : if(hash2[s[left]] <= hash1[s[left]]) count–; //计数–
hash2[s[left]]–;//出窗口
left++;； 出判断循环里面后更新结果。
注意 ： 计数-- 操作需要在出窗口之前， 举例 ：s = “abac” , p = ‘’ ac "; 第二次进入if判断里面 ，定长窗口暂时为【bac】，
如果先 hash2[s[left]]–;的话，那个b存的hash值就变为0，然后判断 if(hash2[s[left]] <= hash1[s[left]]) count–; 就会成立，然后count就会–； 但是count是s中的滑动窗口 和 p有几个字符相等 ， 这里并不相等，所以就会出错。
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> v;int hash1[128] = {0}; //标记pint hash2[128] = {0}; //标记sfor(auto ch : p){hash1[ch]++;}int left = 0, right = 0;int count = 0; //s中的滑动窗口 和 p有几个字符相等int ret = 0;while(right < s.size()){hash2[s[right]]++;//进窗口if(hash2[s[right]] <= hash1[s[right]]) count++; //计数++if(right - left + 1 > p.size())//判断， 这是定长滑动窗口{if(hash2[s[left]] <= hash1[s[left]]) count--; //计数--hash2[s[left]]--;//出窗口left++;}if(count == p.size())v.push_back(left);right++;}return v;}
};
3. 串联所有单词的子串
题目链接
这道题和 2 题一样，只不过2题是字母， 而这个每个字母都变成了字符串
变化：
-
滑动窗口需要执行的次数 ： 3
-
left 和 right的移动
移动的步长 为 单词的长度
class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> v;unordered_map<string,int> hash1;for(auto s : words)hash1[s]++;int len = words[0].size();for(int i = 0; i < len; i++){int left = i, right = i;int count = 0;unordered_map<string,int> hash2;while(right < s.size()){hash2[s.substr(right,len)]++; //进窗口if(hash2[s.substr(right,len)] <= hash1[s.substr(right,len)])count++;while(right - left + 1 > len * words.size())//判断 , 定长滑动窗口{if(hash2[s.substr(left,len)] <= hash1[s.substr(left,len)]) //出窗口count--;hash2[s.substr(left,len)]--;left+=len;}if(count == words.size()) // 更新数据v.push_back(left);right+=len;}}return v;}
};