送给大家一句话：
在最黑暗的那段人生，是我自己把自己拉出深渊。没有那个人，我就做那个人。——中岛美嘉
滑动窗口进阶
前言
继续学习滑动窗口问题。
入门篇我们了解滑动窗口的原理和算法思路：
- 双指针如果同方向移动即可使用滑动窗口
- 滑动窗口的原理是数组的单调性
- 基本步骤：进窗口-判断-出窗口-更新结果
接下来我们继续巩固我们的算法思维。来看三道题目：
Leetcode 1658. 将 x 减到 0 的最小操作数
上连接 ！！！1658. 将 x 减到 0 的最小操作数
题目描述
根据描述，就是从左右两边分别取数，直到x减到零。来看一个样例：
- 输入：nums = [3,2,20,1,1,3], x = 10
- 输出：5
- 解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
算法思路
来看最最最直接的算法：暴力枚举！！！因为只能取两头的元素，所以等价于中间留下的值的和恰好等于数组和减去x。那这样遍历所有的子串，找到最小的即可！！！
怎么进行优化呢？当然是使用单调性来进行优化：
每次我们统计一个子串的和时，想一想right有必要回到 left++ 然后从新开始遍历吗？
当然不用！！！
因为left 到 right 就不满足要求（中间留下的值的和大于数组和减去x），left++后right从left开始最终也会回到原来位置，所以没有必要。
那这样就形成了滑动窗口：
class Solution { public: int minOperations(vector<int>& nums, int x) { //进窗口 //判断 //出窗口 //求和 int sum = 0; for(auto s:nums) sum += s; int tmp = 0;//中间量 int ans = INT_MAX; //特殊情况处理 if(sum - x == 0) return nums.size(); if(sum - x < 0) return -1; int n = nums.size(); for(int left = 0,right = 0;right < n;right++) { //进窗口 tmp += nums[right]; //判断 while(sum - x < tmp && left < right) { //出窗口 tmp -= nums[left]; // left++; } //更新结果 if(sum - x == tmp) ans = min(ans,n - (right - left +1)); } return ans == INT_MAX ? -1 : ans; } };
这样完美解决！！！
过啦！！！
Leetcode 904. 水果成篮
家人们 ！跟上我们的节奏！！！ 904. 水果成篮
题目描述
这道题很有意思奥（奇怪的农场主人…）
根据题目描述，我们需要找到一个子串中（只能有两种水果）的最大长度！来看一个样例：
- 输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
- 输出：5
- 解释：可以采摘 [1,2,1,1,2] 这五棵树。只有两种水果并且最长！
算法思路
直接来最暴力的算法：暴力枚举。遍历所有的子串找到符合条件的最长字串即可（当然肯定会超时！！！）
那么怎么进行优化呢？？？(当然是滑动窗口)
每次找到不符合条件的子串，有没有必要将right指向left呢？？？
当然没有！！！ 最长的已经遍历过，从头开始完全没有必要！！！
1,2,1,1,2,3 不和条件 就没有必要重新遍历2,1,1,2,3
这里的判断方法借助哈希算法来解决：
class Solution { public: int totalFruit(vector<int>& f) { //进窗口 //判断 //出窗口 //更新答案 //用来统计水果种数 int hash[100001] = {0} , ret = 0; int n = f.size(); //滑动窗口 for(int left = 0,right = 0,kinds = 0 ; right < n;right++){ //进窗口 //如果哈希表中是0 那说明是新品种 if(hash[f[right]] == 0) kinds++; hash[f[right]]++; //判断 while(kinds > 2){ hash[f[left]]--; //出窗口前要检查种类是否变化 if(hash[f[left]] == 0) kinds--; left++; } //更新结果 ret = max(ret,right - left + 1); } return ret; } };
提交看一下：过啦！！！！！！！！！
Leetcode 438. 找到字符串中所有字母异位词
家人们！上车！！！438. 找到字符串中所有字母异位词
题目描述
这道题很有说法！
根据题目描述，寻找字符串中与 s 组成元素相同的子串。来看一个样例：
- 输入: s = “abab”, p = “ab”
- 输出: [0,1,2]
- 解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
描述很简单奥
算法思路
不必多说，最简单的算法肯定是暴力枚举！
那么然后进行优化呢？？？
遇见不符合的新字母，right肯定没有必要回到left(根据前面的算法)。所以直接使用滑动窗口即可。
但是这道题的还有一个难点：如何来进行判断是不是一个字符串的异位词呢？？？
我的第一种思路是排序算法，先将 p 进行排序。然后之后的每次的子串都排序与之比较：
class Solution { public: vector<int> findAnagrams(string s, string p) { //先排序，方便比较 sort(p.begin(), p.end()); //unordered_map<string,int> hash; //答案 vector<int> ans; int n = s.size(); //进窗口 for (int left = 0, right = p.size() - 1; right < n; right++, left++) { string tmp = ""; for (int i = left; i <= right; i++) { tmp += s[i]; } sort(tmp.begin(), tmp.end()); if (strcmp(tmp.c_str(), p.c_str()) == 0) ans.push_back(left); } return ans; } };
虽然可以通过简单的测试用例，但是这样有一个巨大的弊端，时间复杂度与p的长度成正比（O(nlogn)）。看这个测试样例
s 有这么这么长！！！！
s = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef
更离谱的是 p 也老长！！！
p = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghi
你说我们这样简单算法怎么可能会不超时呢！?
那应该怎么办呢???
同样也是哈希算法，因为只有小写字母，我们创建一个hash[26]就够用了，然后每次长度与p一致，就一一比较就可以了。
来看暴力解法：
class Solution { public: vector<int> findAnagrams(string s, string p) { int hash1[26] = {0}; for(auto ch:p){ hash1[ch - 'a']++; } //答案 vector<int> ans; int n = s.size(); for (int left = 0, right = p.size() - 1; right < n; right++, left++) { //string tmp = ""; int hash2[26] = {0}; for(int i = left;i <= right ;i++){ hash2[s[i]-'a']++; } int flag = 1; //每次进行判断 for(int i = 0;i < 26;i++){ if(hash1[i] != hash2[i]) flag = 0; } if(flag == 1){ ans.push_back(left); } } return ans; } };
这个可以通过我们的题目但是时间是480ms,还是不够好，这是为什么呢？？？因为这里我们没有进行滑动窗口的算法核心：跳过不必要的子串，即对哈希表进行抽象的滑动窗口，每次我们没有必要重新遍历子串。对哈希表进行动态处理即可：
class Solution { public: vector<int> findAnagrams(string s, string p) { int hash1[26] = {0}; for(auto ch:p){ hash1[ch - 'a']++; } //答案 vector<int> ans; int n = s.size(); int hash2[26] = {0}; //进窗口 for (int left = 0, right = 0; right < n; right++) { //string tmp = ""; //进窗口 hash2[s[right]-'a']++; //满足p的长度 才开始进行 if(right - left + 1 == p.size()){ //判断 int flag = 1; for(int i = 0;i < 26;i++){ if(hash1[i] != hash2[i]) flag = 0; } if(flag == 1){ ans.push_back(left); } //出窗口 //将nums[left]移出哈希表即可 hash2[s[left] -'a']--; left++; } } return ans; } };
这样的运算时间就直接来到了 3ms 简直就是降维打击！！！
当然还可以继续优化，我们来看每次检查哈希表的工作是不是简单遍历检查，但是我们不一定有26个字母需要检查！！！所以我们可以设置一个新变量count用来比较有效字母个数：
- 设置两个哈希表 分别是 p 的对应字母哈希表和子串的对应字母哈希表
- 每次进窗口的元素（ in ）的同时对count进行维护（++hash2[ in - ‘a’ ] <= hash1[ in - ‘a’ ] 就要 ++），只要所需的字母个数大于等于子串的对应字母个数，有效字母就加一
- 出窗口的元素（out）同理（hash2[ out - ‘a’]-- <= hash1[ out - ‘a’] 这样进行减一）, 如果对应字母的个数大于所需的字母个数，那么就是无效字符，不需要减一。
- 如果count == 所需的字母总数，那么进行更新结果。
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> ret; int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数 for (auto ch : p) hash1[ch - 'a']++; int hash2[26] = { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数 int m = p.size(); for (int left = 0, right = 0, count = 0; right < s.size(); right++) { char in = s[right]; // 进窗⼝ + 维护 count if (++hash2[in - 'a'] <= hash1[in - 'a']) count++; if (right - left + 1 > m) // 判断 { char out = s[left++]; // 出窗⼝ + 维护 count if (hash2[out - 'a']-- <= hash1[out - 'a']) count--; } // 更新结果 if (count == m) ret.push_back(left); } return ret; } };
这样的优化对于该题的提升是有限的，但是这是一种非常实用的算法，以后还会遇见哦！！！
送给大家一句话：
在最黑暗的那段人生，是我自己把自己拉出深渊。没有那个人，我就做那个人。——中岛美嘉
