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

   

 

---

  水果成篮  

---

水果成篮

---

 

  题目描述  

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

• 因为当我们在两个果篮都装有水果的情况下，如果再走到下一颗果树，果树的水果种类不是果篮中的任意一种，则停止采摘；
• 所以就是要找出一块连续的区域，这个连续的区域最多有两种类型的元素，并且在所有找到的符合条件的区域中，找出长度最长的区域；

通过上述例子，我们可以把题目描述最终简化成一个问题模型：

找出长度最长的子数组，子数组中的元素种类<=2

---

  解法：滑动窗口  

• 定义 left 指针固定一个起点，然后定义 right 指针向后枚举；
• 枚举出所有合适的子数组，然后返回所有子数组中长度最长的数组 ；

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

如果想不清楚进窗口和出窗口该怎么操作，就回到暴力枚举的基础上，来模拟出进出窗口的操作：

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

Map 官方文档

---

    编写代码： 

 

    分析错误原因： 

• 因为出窗口这行代码的逻辑，是更新 kinds 中的计数；
• 如果放到 if 的下面，那么在检查计数为空之前，如果 output 对应的计数原本就是1，那么 if 条件在更新之前就会检查一个过时的值（即1，而不是更新后的0）；
• 意味着，可能 remove 操作不能被正确的执行，所以会报错；
• 因此，出窗口的操作必须在 if 的前面去更新；

  正确写法  

  方法一：使用容器 Map  

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

根据题目给的上述提示，为了降低执行用时，我们可以通过一个数组模拟哈希表

---

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

---

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

---

 

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

对于这两个字符数相同的字符串，我们如何判断这两个字符串是一个异位词呢？

---

我们可以先分别对 这两个字符串 的 所有字符 进行排序，然后使用 双指针 依次比对这两个字符串对应的字符即可；

这个方法虽然可以达到目的，但是因为排序操作，使得时间复杂度太高了；

所以，如果是两个字符数相同的字符串，要比较是不是异位词，我们可以统计每一个字符出现的个数即可，因为异位词是不考虑顺序的。

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

   暴力解法   

   总结规律   

所以这个枚举的过程，都是从左到右枚举的，所以可以用滑动窗口的解法来解决：

   解法：滑动窗口 + 哈希表   

---

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

---

1. left = 0 , right = 0;
2. 定义 hash1 统计 p 字符串中字符的 key，val
3. 进窗口（定义 hash2，right++，hash2.get(s[ right ])++）
4. 判断（right - left + 1 > m）（因为窗口大小固定，left 只需要移动一次，所以判断不用写成循环））
5. 出窗口（hash2.get(s[ right ])--，left++，）
6. 更新结果 （ check(hash1，hash2) ，返回 true，子串的首元素下标放入返回的 list 中）
7. 循环 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() 的判断方法的步骤   

1. 进窗口：进窗口后，判断 hash2[ input ] <= hash1[ input ]  —> count++
2. 出窗口：出窗口前，判断  hash2[ input ] <= hash1[ input ] —> count--
3. 更新结果：只需要判断 count 是否等于 p.length，是则把当前 left 更新到 list 中

---

   优化后： 

   正确代码： 

   注意：序号一   原因：序号二   

---