解法一：
暴力解法，遍历，每次移动目标字符串的长度，将框出来的排序后字符串和排序后目标字符串进行比较，如果相等则保存其id，但是时间复杂度较高，差点超时。
class Solution:def findAnagrams(self, s: str, p: str):n_str = len(s)n_chistr = len(p)result = []# 对 p 进行一次排序，之后不再排序sorted_p = ''.join(sorted(p))for i in range(n_str - n_chistr + 1): # 只有在足够长度时才开始# 取子串并排序sub_s = s[i:i+n_chistr]if ''.join(sorted(sub_s)) == sorted_p:result.append(i)return result
解法二：
这里介绍时间击败95%的解法，滑动窗口+哈希表。
因为是要选子串，所以用滑动窗口减少时间复杂度。
由于要比较字符串是否相等，而且都是小写字母，所以用哈希统计字符次数。
因为字符串中的字符全是小写字母，可以用长度为26的数组记录字母出现的次数
设n = len(s), m = len(p)。记录p字符串的字母频次p_cnt，和s字符串前m个字母频次s_cnt
若p_cnt和s_cnt相等，则找到第一个异位词索引 0
继续遍历s字符串索引为[m, n)的字母，在s_cnt中每次增加一个新字母，去除一个旧字母
判断p_cnt和s_cnt是否相等，相等则在返回值res中新增异位词索引 i - m + 1
class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:n=len(s)m=len(p)result=[]#如果输入小于目标字符串，则直接返回if n<m:return []#初始字母统计表s_cnt=[0]*26p_cnt=[0]*26#先框住前m个for i in range(m):#字符减掉a相当于按字母表统计s_cnt[ord(s[i])-ord('a')]+=1p_cnt[ord(p[i])-ord('a')]+=1#如果相等，说明第一个框子是正确的，则添加索引0if s_cnt==p_cnt:result.append(0)for i in range(m,n):#退掉坐标的字符s_cnt[ord(s[i-m])-ord('a')]-=1s_cnt[ord(s[i])-ord('a')]+=1if s_cnt==p_cnt:#这里是要添加开头的索引，由于i-m为退掉的索引，所以字符串开始的索引为i-m+1result.append(i-m+1)return result
