[数据结构与算法]leetcode 438

思路一：滑动窗口+哈希数组

1.为两个字符串设置长度为26的哈希字母数组sdup[26]和pdup[26]

2.获得s串长度slen和p串长度plen

3.遍历p串，获得pdup

（1）遍历s串，维护一个元素个数为plen的字串t，维护其元素出现次数的哈希表sdup，也就是每遍历一个新的元素，在sdup数组中，将字串t第一个元素的记录-1，然后找到新元素的位置，相应记录+1；

（2）然后比较sdup和pdup是否相等，若相等，则将t的起始位置加入结果vector中

代码：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int plen=p.length();
        int slen=s.length();
        vector<int> res;
        vector<int> pdup(26,0);
        vector<int> sdup(26,0);
        for(int i=0;i<plen;i++)
        {
            pdup[p[i]-'a']++;
        }
        for(int i=0;i<slen;i++)
        {
            if(i>=plen)
                sdup[s[i-plen]-'a']--;
            sdup[s[i]-'a']++;
            int flag=0;
            for(int j=0;j<26;j++)
            {
                if(sdup[j]!=pdup[j])
                {
                    flag=1;
                    break;
                }
            }
            if(!flag)
                res.push_back(i-plen+1);
        }
        return res;
    }
};

思路二：可变长度滑动窗口+双指针

1.为两个字符串设置长度为26的哈希字母数组sdup[26]和pdup[26]

2.获得s串长度slen和p串长度plen

3.遍历p串，获得pdup

4.起始窗口左端left=0,右端=0

（1）遍历s串，维护一个变长字串t，每当遍历一个新的元素，记为cur_right,则在sdup中找到其相遇位置，对应记录+1

（2）当sdup[cur_right]>pdup[cur_right]时，这意味着t串中cur_right位置上的元素个数是多的，需要减少，我们通过从头开始遍历t串以减去t串中cur_right位置上相同元素以达到满足sdup=pdup，通过sdup[left]–，left++来实现，从而达到左窗口右移的效果。

（3）只要sdup[cur_right]>pdup[cur_right]存在，都会导致sdup!=pdup，这就意味着，此时t串仍然有多余重复元素，假设此时t串长度为tlen<=plen，如果当前t串的最右侧元素是多余重复元素，那么此时的left不可能是目标串的起点，最极端情况就是left==cur_right才满足sdup[cur_right]=pdup[cur_right]。

（4）当sdup[cur_right]<=pdup[cur_right]，判断此时t长度是否刚好等于plen，若是，则找到一个匹配子串，则将t的起始位置加入结果vector中。

补充：对于（4）实际上如果sdup[cur_right]<pdup[cur_right]，

此时t长度是否刚好不可能等于plen，因为至少还有一个元素没有满足个数要求。

代码：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int plen=p.length();
        int slen=s.length();
        vector<int> res;
        vector<int> pdup(26,0);
        vector<int> sdup(26,0);
        for(int i=0;i<plen;i++)
        {
            pdup[p[i]-'a']++;
        }
        int left=0;
        for(int i=0;i<slen;i++)
        {
            sdup[s[i]-'a']++;
            while(sdup[s[i]-'a']>pdup[s[i]-'a'])
            {
                sdup[s[left]-'a']--;
                left++;
            }
            if(i-left+1==plen)
            {
                res.push_back(left);
            }
        }
        return res;
    }
};