LeetCode 438. Find All Anagrams in a String. Tags: 滑动窗口sliding window，hash table

题目链接：

力扣

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
 

Constraints:

1 <= s.length, p.length <= 3 * 104
s and p consist of lowercase English letters.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的解答：

#include<bits/stdc++.h>
using namespace std;


class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;

        int lenS = s.length();
        int lenP = p.length();
        if(lenS < lenP) return result;
        // sliding window, 哈希表。统计字符串s的滑动窗口里的各字符出现次数
        vector<int> window(26, 0);

        // 统计字符串p各个字符出现的次数
        vector<int> pCount(26, 0);

        for(int i = 0; i < lenP; i ++){
            window[s[i] - 'a'] ++;
            pCount[p[i] - 'a'] ++;
        }

        // 滑动窗口的左右索引
        int left = 0;
        int right = lenP - 1;
        for(; right < lenS; right ++, left++){
            if(isAnagram(window, pCount)){
                result.push_back(left);
            }
            window[s[left] - 'a'] --;
            if(right + 1 < lenS){
                // 小心right + 1，字符串索引访问越界
                window[s[right + 1] - 'a'] ++;
            }
            
        }

        return result;
    }

    bool isAnagram(vector<int>& window, vector<int>& pCount){
        for(int i = 0; i < 26; i ++){
            if(window[i] != pCount[i]) return false;
        }
        return true;
    }
};