438. 找到字符串中所有字母异位词#

1
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，
2

3
返回这些子串的起始索引。不考虑答案输出的顺序。
4

5
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
6

7

8

9
示例 1:
10

11
输入: s = "cbaebabacd", p = "abc"
12
输出: [0,6]
13
解释:
14
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
15
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
16
 示例 2:
17

18
输入: s = "abab", p = "ab"
19
输出: [0,1,2]
20
解释:
21
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
22
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
23
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
24

25

26
提示:
27

28
1 <= s.length, p.length <= 3 * 104
29
s 和 p 仅包含小写字母

1
class Solution {
2
public:
3
    vector<int> findAnagrams(string s, string p) {
4
        vector<int> ans;
5
        int n = s.size(), m = p.size();
6
        if(n < m) return ans;
7
        vector<int> sin(26, 0);
8
        vector<int> pin(26, 0);
9
        for(int i = 0; i < m; i++)
10
        {
11
            pin[p[i] - 'a']++;
12
        }
13
        int l = 0;
14
        for(int r = 0; r < n; r++)
15
        {
16
            sin[s[r] - 'a']++;
17
            if(r >= m)
18
            {
19
                sin[s[l] - 'a']--;
20
                l++;
21
            }
22
            if(pin == sin) ans.push_back(l);
23
        }
24
        return ans;
25
    }
26
};