1.题目
题目分析:
题目会给俩个数组,要在大的数组里面去找跟小的数组元素种类一样的子数组,并返回大数组中满足情况的第一个元素地址,就像例子1的abc和cba元素种类一样,就返回第一个元素的地址就行
2.算法原理
题目给定子数组大小是一定的,也就是说在大数组遍历时,就会有个数限制,因为是俩个边界且移动方向是一致的,就可以用滑动窗口,用一个数来计数边界内种类个数,一开始先移动n(限制的种类数大小)下,然后接下来就是n+1个,就要排除元素,那么排除元素还需要判断排的这个元素是否是唯一,如果是唯一就要把种类个数-1,不是就不该变种类个数,然后要插入结果就需要种类数量一致且边界大小一致才行,插入元素要判断是否是第一个进来的,是第一个就要把种类数+1,不然就不变。
排除元素需要注意是先判断删除的元素是否唯一,如果是的话就把种类个数-1,然后把元素排出,如果是先-1的话,再去判断就会导致把元素种类-1,但是它是先-1才变成唯一的,删除后还有一个存在,而就把种类-1了就是错误的。
3.代码实现
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26]={0};int n=p.size();for(char s:p) hash1[s-'a']++;int count=0;int hash2[26]={0};for(int left=0, right=0;right<s.size();right++){char in=s[right];if(++hash2[in-'a']<=hash1[in-'a']) count++;if(right-left+1>n){char out=s[left++];if(hash2[out-'a']--<=hash1[out-'a']) count--;}if(count==n) ret.push_back(left);}return ret;}
};