⽔果成篮
904. 水果成篮 - 力扣（LeetCode）
相当于求数字种类不超过2的最长字字符串
我们先看一看例4.从第一个元素开始最长字符串3331，下一次从第二个位置数吗？没必要，因为只有当字符串中数字种类变为1时，字符串长度才可以增加。
这样我们可以用滑动窗口来解决
怎么判断字符串中数字种类是否变为1？
可以用哈希表map<int,int>里面存入数字的种类以及个数。当该种类的个数==0时，就可以删除它。
class Solution {
public:int totalFruit(vector<int>& f) {int left=0,right=0,len=0;unordered_map<int,int> hash;for(;right<f.size();right++){hash[f[right]]++;while(hash.size()==3){hash[f[left]]--;if(hash[f[left]]==0) hash.erase(f[left]);left++;}len=max(len,right-left+1);}return len;}
};可以用数组代替哈希表，效率更高
class Solution {
public:int totalFruit(vector<int>& f) {int len=0;int hash[100001]={0};for(int left=0,right=0,k=0;right<f.size();right++){if(hash[f[right]]==0)k++;hash[f[right]]++;while(k>2){hash[f[left]]--;if(hash[f[left]]==0) k--;left++;}len=max(len,right-left+1);}return len;}
};找到字符串中所有字⺟异位词
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
异位词 两个子串字母数一样，但顺序可以不一样。
思路一：遍历s每p.size()个字符和p比较是否相等。
建立哈希表h2存入p字符串，哈希表h中存放与p字符串等长的s的子字符串，比较h和h2是否相同，从第一个开始直到最后。
class Solution {
public:vector<int> findAnagrams(string s, string p) {unordered_map<char,int> h;vector<int> v={};for(auto o:p) h[o]++;unordered_map<char,int> h2;for(int i=0;i<p.size();i++){h2[s[i]]++;}for(int left=0,right=(int)p.size()-1;right<(int)s.size();){if(h2==h) v.push_back(left);h2[s[left]]--;if(h2[s[left]]==0)h2.erase(s[left]);left++;right++;h2[s[right]]++;}return v;}
};思路二：我们没有必要每次都进行比较，我们可以用count记录h中有多少个有效字符，什么是有效字符？我们知道异位词 两个子串字母数一样，但顺序可以不一样。所以我们要保证h和h2中对应字母个数相同就可以，如果进入h的字符正好是缺少的字符count++，删除的字符如果不是多余的count--
比如说h2中有3个a 1个b h为空，进入一个a，count++,进入一个b，count++,再进入一个b，
此时h中b的个数>=h2的个数，count就不能++。
当count==p.size()时，就说明h==h2
class Solution {
public:vector<int> findAnagrams(string s, string p) {int h[26]={0};int h2[26]={0};vector<int> v;for(auto o:p){h2[o-'a']++;}int k=p.size();for(int right=0,left=0,count=0;right<s.size();right++){if(++h[s[right]-'a']<=h2[s[right]-'a']) count++;if(right-left+1>k){if(h[s[left]-'a']--<=h2[s[left]-'a']) count--;left++;}if(count==k) v.push_back(left);}return v;}
};
