一.水果成蓝题目链接438. 找到字符串中所有字母异位词 - 力扣LeetCode题目描述i是树的位置第几棵树fruits[i]是这棵树上的水果品种编号。fruits[0] 1表示第 0 棵树上是 1 号水果fruits[2] 1表示第 2 棵树上也是 1 号水果——同一种水果可以种在多棵树上这里面的内容看起来很拗口简单来说就是一句话你有一排果树从左往右走手里最多只能拿两种水果问最多能摘多少棵。第一步只走一遍用一个窗口想象你有一个可以伸缩的“窗口”从左往右滑过整个数组。窗口里的内容就是你已经摘到的水果。规则窗口里最多只能有两种数字。一旦出现第三种窗口左边就得缩直到只剩两种为止。窗口在数组上滑动[1, 2, 1, 3, 2] ↑ left/right一开始窗口只有一个数字1合法长度1。第二步右边界一直往右伸右边界往右走把新数字拉进来。​[1, 2, 1, 3, 2] ↑ ↑ left right​窗口[1,2,1]里有1和2两种合法长度3。第三步当出现第三种时左边界往右缩右边界继续走[1, 2, 1, 3, 2] ↑ ↑ left right窗口[1,2,1,3]里有1、2、3三种不合法了。怎么办咱就左边开始缩text[1, 2, 1, 3, 2] ↑ ↑ left right窗口[2,1,3]还是有1、2、3三种继续缩[1, 2, 1, 3, 2] ↑ ↑ left right窗口[1,3]只有1和3两种合法了。当前长度2。第四步继续往前走右边界继续走[1, 2, 1, 3, 2] ↑ ↑ left right窗口[1,3,2]有1、2、3三种又不合法了缩左边[1, 2, 1, 3, 2] ↑ ↑ left right窗口[3,2]只有3和2两种合法长度2。整个过程走完了最长的长度是3。算法原理滑动窗⼝算法思路研究的对象是⼀段连续的区间可以使⽤滑动窗⼝思想来解决问题。让滑动窗⼝满⾜窗⼝内⽔果的种类只有两种。做法右端⽔果进⼊窗⼝的时候⽤哈希表统计这个⽔果的频次。这个⽔果进来后判断哈希表的⼤⼩如果⼤⼩超过 2说明窗⼝内⽔果种类超过了两种。那么就从左侧开始依次将⽔果划出窗⼝直到哈希表的⼤⼩⼩于等于 2然后更新结果如果没有超过 2说明当前窗⼝内⽔果的种类不超过两种直接更新结果 ret。算法流程a. 初始化哈希表 hash 来统计窗⼝内⽔果的种类和数量b. 初始化变量左右指针 left 0right 0记录结果的变量 ret 0c. 当 right ⼩于数组⼤⼩的时候⼀直执⾏下列循环i. 将当前⽔果放⼊哈希表中ii. 判断当前⽔果进来后哈希表的⼤⼩•如果超过 2将左侧元素滑出窗⼝并且在哈希表中将该元素的频次减⼀如果这个元素的频次减⼀之后变成了 0就把该元素从哈希表中删除重复上述两个过程直到哈希表中的⼤⼩不超过 2iii. 更新结果 retiv. right让下⼀个元素进⼊窗⼝d. 循环结束后ret 存的就是最终结果。过程展现class Solution { public: int totalFruit(vectorint f) { unordered_mapint, int hash; // 统计窗口内水果种类和数量 int ret 0; // 记录最大长度 // left和right维护滑动窗口 for (int left 0, right 0; right f.size(); right) { hash[f[right]]; // 1. 进窗口把当前水果加入 while (hash.size() 2) { // 2. 判断种类超过2种 // 3. 出窗口缩左边 hash[f[left]]--; // 左边水果数量减1 if (hash[f[left]] 0) hash.erase(f[left]); // 数量为0就删掉这个键 left; } ret max(ret, right - left 1); // 4. 更新答案 } return ret; } };拆开讲1.准备工作unordered_mapint, int hash; // key是水果种类value是这个种类在窗口里有多少个 int ret 0; // 记录最长长度2.进窗口for (int left 0, right 0; right f.size(); right) { hash[f[right]];right 一步一步往右走把当前水果加到哈希表里。如果原来窗口里没有这个水果hash.size() 就会加1。如果已经有了就只是计数加1。3.判断 出窗口while (hash.size() 2) { hash[f[left]]--; if (hash[f[left]] 0) hash.erase(f[left]); left; }如果窗口里有超过2种水果就要把左边的水果移出去。先把 left 指向的水果计数减1如果减到0了就从哈希表里删掉这个键。然后 left 往右移直到 hash.size() 又变成2为止。4.更新答案ret max(ret, right - left 1);当前窗口是合法的最多2种水果窗口长度是 right - left 1跟之前记录的最大值比一下取大的。二.找到字符串中所有字⺟异位词题目链接438. 找到字符串中所有字母异位词 - 力扣LeetCode题目描述算法原理解法滑动窗⼝ 哈希表算法思路因为字符串 p 的异位词的⻓度⼀定与字符串 p 的⻓度相同所以我们可以在字符串 s 中构造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝并在滑动中维护窗⼝中每种字⺟的数量当窗⼝中每种字⺟的数量与字符串 p 中每种字⺟的数量相同时则说明当前窗⼝为字符串 p的异位词因此可以⽤两个⼤⼩为 26 的数组来模拟哈希表⼀个来保存 s 中的⼦串每个字符出现的个数另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。过程展现:class Solution { public: vectorint findAnagrams(string s, string p) { vectorint 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; } };1.准备工作vectorint ret; // 存结果的数组 int hash1[26] {0}; // 存 p 里每个字母出现了几次 for (auto ch : p) hash1[ch - a]; // 比如 pabchash1[0]1hash1[1]1hash1[2]1 int hash2[26] {0}; // 存当前窗口里每个字母出现了几次 int m p.size(); // 窗口大小固定为 mhash1 是“标准答案”一直不变。hash2 是“当前窗口”实时更新。2.主循环for (int left 0, right 0, count 0; right s.size(); right)left 是窗口左边界right 是右边界count 是有效字符的数量。三个变量一起初始化。3.进窗口char in s[right]; if (hash2[in - a] hash1[in - a]) count;把当前字符加到窗口里hash2 里对应的计数加 1。如果加完后这个字符的数量还没超过 p 里的数量说明这个字符是“有效”的count 加 1。如果超过了说明多出来的这个字符在 p 里没有对应的“空位”了count 不变。4.判断窗口长度是否超了if (right - left 1 m) { char out s[left]; if (hash2[out - a]-- hash1[out - a]) count--; }窗口长度只能等于 m一旦超过左边就得缩。先记住左边的字符然后 left 加 1。接着判断这个字符在移除之前是不是“有效”的——如果移除前它的数量没超过 p 里的数量说明它之前贡献了一个 count移除后 count 要减 1。如果移除前已经超过 p 里的数量了说明它之前就是多余的count 本来就没加过移除后也不用减。5.更新答案if (count m) ret.push_back(left);如果有效字符数量等于窗口长度说明窗口里每个字符都刚好对上没有多余的也没有缺的完全匹配。此时 left 就是答案存起来。问题为啥用 count 不用直接比较数组如果直接比较 hash1 和 hash2 两个数组每次要遍历 26 个元素窗口移动一次就比较一次虽然 26 不大但 s 很长的时候还是有开销。用 count 记录有效字符数判断是否匹配只需要 O(1) 时间更快。整个流程走一遍s cbaebabacdp abcm 3窗口滑到 cbahash2 里 c、b、a 各 1都 ≤ hash1count3countm记录 left0窗口滑到 baehash2 里 a:1、b:1、c:0、e:1e 的 hash1 是 0所以 e 不算count2不匹配窗口滑到 ebae 不算b 和 a 算count2不匹配窗口滑到 baba:1、b:2b 有两个但 hash1 里 b 只有 1第二个 b 不算count2不匹配窗口滑到 bacb:1、a:1、c:1都 ≤ hash1count3匹配记录 left6最终返回 [0, 6]。三.串联所有单词的⼦串题目链接30. 串联所有单词的子串 - 力扣LeetCode题目描述算法原理算法思路如果我们把每⼀个单词看成⼀个⼀个字⺟问题就变成了找到字符串中所有的字⺟异位词。⽆⾮就是之前处理的对象是⼀个⼀个的字符我们这⾥处理的对象是⼀个⼀个的单词。过程展现:class Solution { public: vectorint findSubstring(string s, vectorstring words) { vectorint ret; unordered_mapstring, int hash1; // 保存 words ⾥⾯所有单词的频次 for (auto s : words) hash1[s]; int len words[0].size(), m words.size(); for (int i 0; i len; i) // 执⾏ len 次 { unordered_mapstring, int hash2; // 维护窗⼝内单词的频次 for (int left i, right i, count 0; right len s.size(); right len) { // 进窗⼝ 维护 count string in s.substr(right, len); hash2[in]; if (hash1.count(in) hash2[in] hash1[in]) count; // 判断 if (right - left 1 len * m) { // 出窗⼝ 维护 count string out s.substr(left, len); if (hash1.count(out) hash2[out] hash1[out]) count--; hash2[out]--; left len; } // 更新结果 if (count m) ret.push_back(left); } } return ret; } };1.准备工作vectorint ret; unordered_mapstring, int hash1; for (auto s : words) hash1[s]; int len words[0].size(), m words.size();ret 存结果。hash1 存 words 里每个单词出现了几次比如 words [foo, bar, foo]那 hash1[foo] 2hash1[bar] 1。len 是每个单词的长度m 是单词个数。总共要匹配的长度是 len * m。2.为什么要循环 len 次for (int i 0; i len; i)这是这题比较绕的地方。因为窗口每次移动一个单词len 个字符但 s 的开头不一定正好是某个单词的边界。比如 s barfoothefoobarmanlen 3单词边界在位置 0、3、6、9... 但如果 s 是 xbarfoo...那从位置 0 开始就切不对了。所以要从 0、1、2len-1分别开始滑一次覆盖所有可能的起始位置。这样就不会漏掉答案了。3.每个起始位置单独滑unordered_mapstring, int hash2; for (int left i, right i, count 0; right len s.size(); right len)hash2 存当前窗口里单词的频次。left 和 right 从 i 开始每次走 len 步一个单词的长度。count 记录窗口里已经匹配上的单词数量。为什么 right len s.size()保证取子串的时候不越界。4.进窗口string in s.substr(right, len); hash2[in]; if (hash1.count(in) hash2[in] hash1[in]) count;取当前单词 in加到 hash2 里。如果这个单词在 hash1 里存在并且窗口中这个单词的数量没超过它在 words 里的数量说明这个单词是“有效”的count。如果超了说明这个单词是多出来的不算。5.判断窗口是否超长if (right - left 1 len * m) { string out s.substr(left, len); if (hash1.count(out) hash2[out] hash1[out]) count--; hash2[out]--; left len; }窗口长度只能等于 len * m一旦超过左边就要缩。先取左边要出去的单词 out如果它是有效单词在 hash1 里存在且数量没超过count--。然后把 hash2 里 out 的计数减 1left 右移一个单词长度。6.更新结果if (count m) ret.push_back(left);如果有效单词数等于 m说明窗口里所有单词都匹配上了left 就是答案。四.最⼩覆盖⼦串题⽬链接76. 最小覆盖子串 - 力扣LeetCode题目描述算法原理解法滑动窗⼝ 哈希表算法思路研究对象是连续的区间因此可以尝试使⽤滑动窗⼝的思想来解决。如何判断当前窗⼝内的所有字符是符合要求的呢我们可以使⽤两个哈希表其中⼀个将⽬标串的信息统计起来另⼀个哈希表动态的维护窗⼝内字符串的信息。当动态哈希表中包含⽬标串中所有的字符并且对应的个数都不⼩于⽬标串的哈希表中各个字符的个数那么当前的窗⼝就是⼀种可⾏的⽅案。算法流程a. 定义两个全局的哈希表 1 号哈希表 hash1 ⽤来记录⼦串的信息 2 号哈希表 hash2⽤来记录⽬标串 t 的信息b. 实现⼀个接⼝函数判断当前窗⼝是否满⾜要求i. 遍历两个哈希表中对应位置的元素• 如果 t 中某个字符的数量⼤于窗⼝中字符的数量也就是 2 号哈希表某个位置⼤于1 号哈希表。说明不匹配返回 false • 如果全都匹配返回 true 。主函数中a. 先将 t 的信息放⼊ 2 号哈希表中b. 初始化⼀些变量左右指针 left 0right 0 ⽬标⼦串的⻓度 len INT_MAX ⽬标⼦串的起始位置 retleft 通过⽬标⼦串的起始位置和⻓度我们就能找到结果c. 当 right ⼩于字符串 s 的⻓度时⼀直下列循环i. 将当前遍历到的元素扔进 1 号哈希表中ii. 检测当前窗⼝是否满⾜条件• 如果满⾜条件1) 判断当前窗⼝是否变⼩。如果变⼩更新⻓度 len 以及字符串的起始位置retleft 2) 判断完毕后将左侧元素滑出窗⼝顺便更新 1 号哈希表3) 重复上⾯两个过程直到窗⼝不满⾜条件iii. right 遍历下⼀个元素d. 判断 len 的⻓度是否等于 INT_MAX i. 如果相等说明没有匹配返回空串ii. 如果不想等说明匹配返回 s 中从 retleft 位置往后 len ⻓度的字符串。过程展现class Solution { public: string minWindow(string s, string t) { int hash1[128] {0}; // 统计字符串 t 中每⼀个字符的频次 int kinds 0; // 统计有效字符有多少种 for (auto ch : t) if (hash1[ch] 0) kinds; int hash2[128] {0}; // 统计窗⼝内每个字符的频次 int minlen INT_MAX, begin -1; for (int left 0, right 0, count 0; right s.size(); right) { char in s[right]; if (hash2[in] hash1[in]) count; // 进窗⼝ 维护 count while (count kinds) // 判断条件 { if (right - left 1 minlen) // 更新结果 { minlen right - left 1; begin left; } char out s[left]; if (hash2[out]-- hash1[out]) count--; // 出窗⼝ 维护 count } } if (begin -1) return ; else return s.substr(begin, minlen); } };一板块板块讲1.统计 t 里有哪些字符int hash1[128] {0}; int kinds 0; for (auto ch : t) if (hash1[ch] 0) kinds;hash1 记录 t 里每个字符出现了几次。kinds 记录 t 里有几种不同的字符比如 t ABCkinds 3。后面判断窗口是否覆盖全部字符就是看 count 是否等于 kinds。这里用了一个小技巧hash1[ch] 0如果某个字符第一次出现hash1[ch] 从0变成1等于0成立kinds。如果第二次出现hash1[ch] 从1变成2等于0不成立kinds 不变。这样就把 t 里有多少种不同字符算出来了。2.准备工作int hash2[128] {0}; // 窗口内字符统计 int minlen INT_MAX, begin -1; // 最短长度和起始位置hash2 跟 hash1 结构一样存窗口内每个字符出现了几次。3.进窗口for (int left 0, right 0, count 0; right s.size(); right) { char in s[right]; if (hash2[in] hash1[in]) count;right 往右走把当前字符加入窗口hash2 计数加1。如果加完后这个字符在窗口里的数量刚好等于它在 t 里的数量说明这个字符“达标”了count。注意这里用的是不是。因为 count 记录的是“有多少种字符已经达标了”不是“有多少个字符达标了”。每种字符只要达标一次就够了多出来的不算。4.判断是否可以缩窗口while (count kinds) { // 更新结果 if (right - left 1 minlen) { minlen right - left 1; begin left; } // 出窗口 char out s[left]; if (hash2[out]-- hash1[out]) count--; }如果 count kinds说明窗口里所有种类的字符都达标了当前窗口有效。这时候尝试缩左边看能不能让窗口更短。每次缩之前先把当前窗口长度记录下来如果比之前的最短还短就更新。缩的时候把 left 指向的字符从窗口里移出去。如果移出去之前这个字符的数量刚好等于它在 t 里的数量说明移出去之后这个字符就不达标了count--。如果移出去之前数量已经大于 t 里的数量说明移出去一个还有余量count 不变。5.返回结果return begin -1 ? : s.substr(begin, minlen);如果 begin 还是 -1说明从来没见过有效窗口返回空串。否则从 begin 开始截取 minlen 个字符返回。咱举个例子走一遍s ADOBECODEBANCt ABCt 里 A、B、C 各一个kinds 3right 一直走到 ADOBEC窗口里 A、B、C 都齐了count 3。此时窗口长度6记录 ADOBEC。开始缩左边。left 从 A 开始A 移出去后 A 没了count 变成2。窗口变成 DOBEC不再覆盖全部字符。right 继续走到 CODEB 的时候又齐了但长度5比6短更新为 CODEB。缩左边缩到 ODEB 的时候又不齐了。right 继续走到 BANC 的时候齐了长度4更新为 BANC。继续缩左边ANC 不齐了停。最终答案 BANC长度4。问题补充啥用 count 不用比较数组跟之前一样用 count 就不用每次都遍历128个字符比较 hash1 和 hash2 了。count 记录有多少种字符达标了达标的意思是窗口里这个字符的数量 t 里这个字符的数量。当 count kinds 时说明 t 里所有字符都被窗口覆盖了。用count 判断是 O(1)比较数组是 O(128)虽然128不大但 s 很长的时候还是有差距。