【优选算法 — 滑动窗口】水果成篮 & 找到字符串中全部字母异位词

   

 

---

  水果成篮  

---

水果成篮

---

 

  标题形貌  

由于只有两个篮子，每个篮子装的水果种类雷同，如果从 0 开始摘，则只能摘 0 和 1 两个种类 ；

• 由于当我们在两个果篮都装有水果的情况下，如果再走到下一颗果树，果树的水果种类不是果篮中的恣意一种，则克制采摘；
  
• 以是就是要找出一块一连的地区，这个一连的地区最多有两种范例的元素，而且在全部找到的符合条件的地区中，找出长度最长的地区；
  

通过上述例子，我们可以把标题形貌终极简化成一个题目模子：
找出长度最长的子数组，子数组中的元素种类<=2

---

  解法：滑动窗口  

• 界说 left 指针固定一个出发点，然后界说 right 指针向后罗列；
  
• 罗列出全部符合的子数组，然后返回全部子数组中长度最长的数组 ；
  

• 模仿一个 hash 表 kinds，来统计水果出现的个数；
  
• 每 right 遍历一个元素，就把该元素对应的 kinds[ fruits [ i ] ] ++;
  
• 然后每次改变 kinds的元素 kinds[ fruits [ i ] ] ，都要判断 kinds 这个数组的有效元素个数是否小于3 ；
  

如果想不清晰进窗口和出窗口该怎么利用，就回到暴力罗列的底子上，来模仿出收支窗口的利用：

• left = 0 ，right = 0；new kinds[ ];
  
• 进窗口（kinds[fruit [ right ] ]++，right++）
  
• 循环判断 3，4，5（kinds.length 是否 >2）
  
• 出窗口（kinds[fruit [ left ] ]--，left++）；
  
• 如果由于 kinds[ fruit [ left ] ]--，导致 kinds[fruit [ left ] ] 变成0，则要移除这个元素
  
• 更新效果（不停更新 ret 直到末了拿到最大值）
  

Map 官方文档

---

    编写代码： 
 

    分析错误缘故起因： 

• 由于出窗口这行代码的逻辑，是更新 kinds 中的计数；
  
• 如果放到 if 的下面，那么在查抄计数为空之前，如果 output 对应的计数原来就是1，那么 if 条件在更新之前就会查抄一个逾期的值（即1，而不是更新后的0）；
  
• 意味着，大概 remove 利用不能被精确的实验，以是会报错；
  
• 因此，出窗口的利用必须在 if 的前面去更新；
  

  精确写法  
  方法一：利用容器 Map  

  方法二：用数组模仿哈希表  

根据标题给的上述提示，为了低落实验用时，我们可以通过一个数组模仿哈希表

---

   找到字符串中全部字母异位词   

---

找到字符串中全部字母异位词

---

 

  1.先快速判断两个字符数雷同的字符串是否是“异位词”  

对于这两个字符数雷同的字符串，我们怎样判断这两个字符串是一个异位词呢？

---

我们可以先分别对 这两个字符串 的 全部字符 举行排序，然后利用 双指针 依次比对这两个字符串对应的字符即可；
这个方法固然可以到达目的，但是由于排序利用，使得时间复杂度太高了；

以是，如果是两个字符数雷同的字符串，要比力是不是异位词，我们可以统计每一个字符出现的个数即可，由于异位词是不思量次序的。

以是我们可以通过哈希表，快速判断两个词是否是异位词:

   暴力解法   

   总结规律   

以是这个罗列的过程，都是从左到右罗列的，以是可以用滑动窗口的解法来办理：

   解法：滑动窗口 + 哈希表   

---

• 之前做的关于滑动窗口的标题，窗口巨细是不固定的，这题是第二种滑动窗口的题型，就是窗口巨细固定（left 和 right 同时移动）；
  
• 只要界说的两个指针从始至终都是同向移动的，就是滑动窗口的题型；
  

---

• left = 0 , right = 0;
  
• 界说 hash1 统计 p 字符串中字符的 key，val
  
• 进窗口（界说 hash2，right++，hash2.get(s[ right ])++）
  
• 判断（right - left + 1 > m）（由于窗口巨细固定，left 只必要移动一次，以是判断不消写成循环））
  
• 出窗口（hash2.get(s[ right ])--，left++，）
  
• 更新效果 （ check(hash1，hash2) ，返回 true，子串的首元素下标放入返回的 list 中）
  
• 循环 3 4 5 6
  

---

   优化 check()    

---

由于 s 和 p 都是小写字母，以是我们只必要创建一个巨细为 26 的数组模仿哈希表即可，数组下标模仿的是哈希表的 key。
那么每次步伐实验到调用 check() 的地方，check()中，仅仅必要比力 26 次每个元素的值是否雷同即可。

---

   时间复杂度    
因此，在上述优化后，时间复杂度 O(26*N) —> O(N)。

---

由于我们这道题，哈希表存的是一个一个的字符，以是我们可以用字符数组来模仿哈希表，这时间，比力两个字符数组黑白常快的；
但是，如果遇到哈希表存的 key，是一个一个的字符串，就不能再用数组模仿哈希表了；

---

   优化 check() 的判断条件   

---

我们如果直接调用 check()，来直接比力两个哈希表是否雷同 ，是必要比力 26 次才可以出效果的；
如果换难一点的题，大概必要比力更多次，才可以知道两个两个哈希表是否雷同，因此我们必要优化 check() 的判断条件;

做法：利用 count 来统计窗口中“有效字符”的个数，肯定要留意有效字符的界说

我们要在进窗口的利用过程中，维护 count；
此时，hash1 和 hash2 的 都有一个 c；
   

• 以是，在往 hash2 添加了一个字符后，这个字符在 hash1 中也有；
  
• 而且这个字符在放入 hash2 后，修改后的个数数字，是小于便是hash1对应字符的个数数字的
  

满意以上两点，就可以称为是“有效字符”，而 count 就是用来统计这些字符的个数的。

right++，如果遍历到的字符放入 hash2 后，对应的 val 大于 hash1，则分析是无效字符，count不更新

此时，我们必要判断一下，count 是否便是3（p.length），如果 count 刚好便是3（p.length），分析此时，窗口中的字符满是有效字符；
以是一边通过进窗口利用更新哈希表，一边可以维护 count；固然，上面说的只是入窗口，出窗口也必要维护 count

---

思索：此时滑动窗口，right 指向新的字符 a，必要更新 count 吗？
是必要的；但是此时的窗口太大了，必要让 left++，而且从 hash2 中移出出窗口的元素；
而且在 left 向后移动的这一步的过程中，第一个 c 变成了多余元素，而第二个 c 变成有效元素；
以是在这一步 left 后挪的过程中，是不改变 count 的值的；

此时的窗口巨细便是 p.length，继承向后移动 right，遍历到的字符 e 加到 hash2 中；

每次 right++ 后，必要再次判断窗口的长度，会发现窗口长度大于 p.length，以是又必要调解 left；

在调解 left 之前，我们必要判断此时的  left  是否是一个有效元素
left 指向的元素在 hash2 的 val ，如果小于便是 hash1 中的对应元素的val，则 left 是有效元素；
对于上图的情况，left 向后移动，删除的元素是一个有效元素，因此 count--；
末了，只必要判断 count 是否与 p.length 相称即可，如许就不必要遍历 26 次了；

---

   总结优化 check() 的判断方法的步调   

• 进窗口：进窗口后，判断 hash2[ input ] <= hash1[ input ]  —> count++
  
• 出窗口：出窗口前，判断  hash2[ input ] <= hash1[ input ] —> count--
  
• 更新效果：只必要判断 count 是否便是 p.length，是则把当前 left 更新到 list 中
  

---

   优化后： 

   精确代码： 

   留意：序号一   缘故起因：序号二   

---