### 438. Find All Anagrams in a String


题目:
<https://leetcode.com/problems/Find-All-Anagrams-in-a-String/>


难度:

Easy



思路

刚开始打算直接遍历整个s，时间复杂度为O(m*n),m和n分别为字符串p和s的长度，但是超时了



```

class Solution(object):  # 此法超时
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        l, res = len(p), []
        for i in range(len(s)):
            if collections.Counter(s[i:i+l]) == collections.Counter(p):
                res.append(i)
        return res
```

于是用双指针，left和right都从0开始往后遍历
```
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        res, cnts = [], [0] * 26
        for c in p:
            cnts[ord(c) - ord('a')] += 1
            left, right = 0, 0
        while right < len(s):
            cnts[ord(s[right]) - ord('a')] -= 1
            while left <= right and cnts[ord(s[right]) - ord('a')] < 0:
                cnts[ord(s[left]) - ord('a')] += 1
                left += 1
            if right - left + 1 == len(p):
                res.append(left)
            right += 1
        return res
```
模板大法好
```python
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        res = []
        if len(p) > len(s):
            return res
        maps = collections.Counter(p)
        counter = len(maps.keys())
        begin, end, head, length = 0, 0, 0, sys.maxint
        while end < len(s):
            if s[end] in maps:
                maps[s[end]] -= 1
                if maps[s[end]] == 0:
                    counter -= 1
            end += 1
            while counter == 0:
                if s[begin] in maps:
                    maps[s[begin]] += 1
                    if maps[s[begin]] > 0:
                        counter += 1
                if end - begin == len(p):
                    res.append(begin)
                begin += 1
        return res
```