解法一:暴力枚举
解法二:滑动窗口+hash表优化
- 定义left和right为起始坐标0,right向后遍历,并加入到哈希表中,
- 然后也要记录下来每次进入哈希表的有效字符(与目标字符串中相同的字符)的个数
- 且这个滑动窗口的长度不能超过目标字符串的长度
- 当超过的时候, left向后移动,且维护count的值
代码:
public List<Integer> findAnagrams(String ss, String pp) {
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
int[] hash1 = new int[26];
//统计p中的字符的个数
for(char ch : p){
hash1[ch - 'a']++;
}
int[] hash2 = new int[26];
int m = p.length;
List<Integer> ret = new ArrayList<>();
for(int left = 0, right = 0,count = 0; right < s.length; right++){
//进窗口
char in = s[right];
if(++hash2[in - 'a'] <= hash1[in - 'a']){
//维护count
count++;
}
//判断
if(right - left + 1 > m){
//出窗口
char out = s[left++];
if(hash2[out - 'a']-- <= hash1[out - 'a']){
//维护count
count--;
}
}
if(count == m){
ret.add(left);
}
}
return ret;
}