【专题刷题】滑动窗口（二）：水果成篮，所有字母异位词，乘积小于 K 的子数组

📝前言说明：

• 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

---

904. 水果成篮

这道题题目容易让人产生歧义。但是通过示例就可以看出来，题目想表达的意思是：
不同数字代表不同类型的水果，求最长子数组，要求这个最长子数组中的不同的数字个数不超过2。

个人解

思路：滑动窗口+哈希表
把题目转换成最长子数组问题，用一个same变量标记子数组内不同的数字的个数。并且用一个map记录每个数字出现的次数。

• 进窗口时，维护same（通过判断进入的是不是新数字）
• 判断：因为是求最长，所以当不满足条件的时候才要出窗口
• 出窗口：更新维护值same，并且出窗口后更新结果

用时：13:00
屎山代码：

class Solution {
public:int totalFruit(vector<int>& fruits) {int n = fruits.size(), ans = 0, same = 2;std::map<int, int> cnt; // 记录每个数字出现的次数for(int left = 0, right = 0; right < n; right++){cnt[fruits[right]]++; // 进窗口if(cnt[fruits[right]] == 1) // 代表是进窗口的是新数字{same--;}while(same < 0) // 判断{if(cnt[fruits[left]] == 1){same++; // 代表出窗口的数字是子数组中最后一个}cnt[fruits[left]]--; // 出窗口left++;}ans = max(ans, right - left + 1);}return ans;}
};

时间复杂度：O(n)
空间复杂度：O(1)

---

优质解：

思路：别人也是滑动窗口+哈希表，不过别人写的更简洁一点，更好的利用了map这个数据结构。（学习一下）
代码（来源：灵茶山艾府）：

class Solution {
public:int totalFruit(vector<int>& fruits) {int ans = 0, left = 0;unordered_map<int, int> cnt; // 比map更快for (int right = 0; right < fruits.size(); right++) {cnt[fruits[right]]++; // fruits[right] 进入窗口while (cnt.size() > 2) { // 直接用cnt.size()来反映子数组中不同数字的个数int out = fruits[left];cnt[out]--; // fruits[left] 离开窗口if (cnt[out] == 0) {cnt.erase(out); // 当没有元素了，直接erase，会把键也删掉，呼应上面的cnt.size()}left++;}ans = max(ans, right - left + 1);}return ans;}
};

---

LCR 015. 找到字符串中所有字母异位词

个人解

思路：
用哈希记录 p 串的每个字母出现的次数。
然后遍历字符串，将每一个和 p 串长度相同的子串的哈希表和 p 串的哈希表进行比较。当相同时就加入答案。
用时：20：00
屎山代码：

class Solution {
public:bool is_change(string s, map<char, int> dict_p){map<char, int> dict_s;for(auto x: s){dict_s[x]++;}for(auto x: dict_p){if(x.second != dict_s[x.first]){return false;}}return true;}vector<int> findAnagrams(string s, string p) {map<char, int> dict_p;for(auto x : p){dict_p[x]++;}int len = p.size(), n = s.size();vector<int> ans;for(int left = 0, right = len - 1; right < n; right++, left++){if(is_change(string(s.begin() + left, s.begin() + right + 1), dict_p)){ans.push_back(left);}}return ans;}
};

时间复杂度：O(nm)，只想到了这个暴力（n是s的长度，m是p的长度，外层循环n次，内层每次比较都需要遍历一个m长度的子串，并且要遍历哈希表【哈希表的元素个数最多为26个】）
空间复杂度：O(dict.size() + ans.size())

---

优质解：

思路：

暴力解法中：遍历肯定是少不了的。通过比较哈希表来判断两个串是否是“异位词”也没办法变。那么能变的就是能不能减少每个子串的哈希表的获取的时间。
因为每次我们都是进入一个字母或者出去一个字母，所以我们只需要每次改变原来哈希表中的一个字母对应的次数就行了！
进窗口：hash2[s[right]]++
判断：窗口长度是否等于 p 的长度
出窗口：hash1[s[left]]--
更新结果：哈希表相同时

代码：

class Solution {
public:bool is_change(int* hash1, int* hash2) {for (int i = 0; i < 26; i++) {if (hash1[i] != hash2[i]) {return false;}}return true;}std::vector<int> findAnagrams(std::string s, std::string p) {std::vector<int> ans;int m = p.size(), n = s.size();if (n < m) return ans; // 如果 s 的长度小于 p，直接返回空结果int hash1[26] = { 0 }, hash2[26] = { 0 };for (auto ch : p) { // p 的哈希表hash1[ch - 'a']++;}for (int left = 0, right = 0; right < n; right++) {hash2[s[right] - 'a']++; // 新字符加入窗口if (right - left + 1 > m) {hash2[s[left] - 'a']--; // 窗口左边界右移，移除最左边字符left++;}if (right - left + 1 == m && is_change(hash1, hash2)) {ans.push_back(left); // 窗口大小等于 p 的长度且满足条件，记录起始索引}}return ans;}
};     

时间复杂度：O(n)
空间复杂度：O(26 + ans.size())

---

713. 乘积小于 K 的子数组

个人解

思路：越短越合法型滑动窗口

• 进窗口：维护窗口内乘积mul
• 判断：当窗口内乘积>=k时要出窗口
• 出窗口：更新mul
• 更新结果：因为出窗口后必然乘积<k

注意两个小点：

1. nums[i]≥1，乘积不可能小于 1，所以当 k≤1 时，没有这样的子数组，直接返回 0。
2. 题目要求的是所有子数组，所以我们要考虑进窗口以后会新增哪些子数组？增加的就是（特有新增nums[right]的），即：以nums[right]为尾的往前长度增加的到nums[left]的这些子数组。

用时：10:00
屎山代码：

class Solution {
public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {int ans = 0, mul = 1; if(k <= 1){return 0;}for(int left = 0, right = 0; right < nums.size(); right++){mul *= nums[right]; // 进窗口while(mul >= k){mul /= nums[left++];}ans += right - left + 1;}return ans;}
};

时间复杂度：O(n)
空间复杂度：O(1)

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！