904. 水果成篮
题目描述：
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
解题思路：
此时right需要向右++，这个时候可能会出现两种情况：
解题代码：
class Solution { public: int totalFruit(vector<int>& fruits) { unordered_map<int,int> hash; int ret=0; for(int left=0,right=0;right<fruits.size();right++) { hash[fruits[right]]++; while(hash.size()>2) { hash[fruits[left]]--; if(hash[fruits[left]]==0) hash.erase(fruits[left]); left++; } ret=max(ret,right-left+1); } return ret; } };
438. 找到字符串中所有字母异位词
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
题目描述：
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
解题思路：
我们先通过暴力解法来分析一下题目：
我们可以遍历s中每个位置，让他们跟p进行判断是否为异位词
我们发现这是一个滑动区间【left，right】的解法，我们来想办法实现其优化
首先我们可以利用哈希表hash1来存储p中每个字符和其个数 ，并且可以在滑动期间中利用hash2来记录s中的字符和个数
我们这里还需要一个变量length=p.size(），以及一个变量count来记录有效字符的个数
1.进窗口——hash2[s[right]]++
if(hash2[s[right]]<=hash1[s[right]]) count++;
2.当right-left+1>length进行判断
3.出窗口——hash2[s[left]]--
if(hash2[s[left]]<=hash1[s[left]]) count--;//在出窗口前更新count
4.更新结果——count==length
!这里的哈希表可以用大小为26的数组代替，并且速度更快
解题代码：
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int>ret; int length=p.size(); unordered_map<char,int>hash1; for(int i=0;i<p.size();i++) hash1[p[i]]++; unordered_map<char,int>hash2; for(int left=0,right=0,count=0;right<s.size();right++) { char ch=s[right]; //进窗口 hash2[ch]++; if(hash2[ch]<=hash1[ch]) count++; //判断 if(right-left+1>length) { char out=s[left]; if(hash2[out]<=hash1[out]) count--;//在出窗口前更新count hash2[out]--;//出窗口 left++; } //更新结果 if(count==length) ret.push_back(left); } return ret; } };
