传送门: https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。

---

分析

异位词，即与给定的p只要所含字符以及所含其字符的数量相同即可。比如"bba"与"bab"即为异位词。

那么如何来判断呢？假设当前一个子串为s1，我们很容易想到通过vector记录他每个字符出现的数量，然后与目标子串p进行比较即可。

又因为这里要求的是连续的子串，所以我们可以通过维护一个长度为p.length()的窗口来求，因为要是异位词必定长度相同。当移动窗口时，只需要将上一位移出去，下一位加进来就可以了。比如"abbaab",假设p.length()=4,一开始为"abba",下一步只需要将第一个a移出，将下一个的a移进来就可以了。

就像上图一样，类似于滑动一个窗口。

Tips:需要特判s.length()<p.length()的情况,此时直接返回空就可以了。

参考代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = s.length(),m = p.length();
        if(n < m)return {};
        vector<int> ans;
        vector<int> cur(26),target(26);
        for(int i = 0;i < m;i++)target[p[i] - 'a']++;
        for(int i = 0;i < m;i++)cur[s[i] - 'a']++;
        if(target == cur)ans.push_back(0);
        for(int i = 1;i <= n - m;i++) {
            cur[s[i - 1] - 'a']--;
            cur[s[i + m - 1] - 'a']++;
            if(cur == target)ans.push_back(i);
        }
        return ans;
    }
};