给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

示例 2:

输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

提示:

1 <= s.length, p.length <= 3 * 10(4)

s 和 p 仅包含小写字母

因为s，p仅包含小写字母所以我们可以用一个定长数组来记录各字母出现次数

维护一个定长滑动窗口，每次移动都与频次数组比较即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int l1 = s.size(), l2 = p.size();
        if (l1 < l2)
            return {};
        vector<int> ss(26, 0);
        vector<int> pp(26, 0);
        for (char c : p)
            pp[c - 'a']++;

        int l = 0, r = l2 - 1;
        for (int i = 0; i < r; i++)
            ss[s[i] - 'a']++;

        vector<int> ans;
        while (r < l1) {
            ss[s[r] - 'a']++;

            if (ss == pp)
                ans.push_back(l);

            ss[s[l] - 'a']--;
            r++;
            l++;
        }
        return ans;
    }
};

为了节省比较，我们可以只维护一个频次数组，正数表示该字母多了，负数表示少了，同时一个变量diff表示字母频次不匹配的字母的个数，这样只要diff=0就可以判断为异位词

每次count变0或从0变为其他更新diff即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();

        if (sLen < pLen)
            return vector<int>();

        vector<int> ans;
        vector<int> count(26);
        for (int i = 0; i < pLen; ++i) {
            ++count[s[i] - 'a'];
            --count[p[i] - 'a'];
        }

        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0)
                ++differ;
        }

        if (differ == 0)
            ans.push_back(0);

        for (int i = 0; i < sLen - pLen; ++i) {
            if (count[s[i] - 'a'] == 1)
                --differ;
            else if (count[s[i] - 'a'] == 0)
                ++differ;
            --count[s[i] - 'a'];

            if (count[s[i + pLen] - 'a'] == -1)
                --differ;
            else if (count[s[i + pLen] - 'a'] == 0)
                ++differ;
            ++count[s[i + pLen] - 'a'];

            if (differ == 0)
                ans.push_back(i + 1);
        }

        return ans;
    }
};