Q：给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
A：
滑动窗口（不过我把代码的s1和s2写反了，原理没错）
public boolean checkInclusion(String s1, String s2) {
if (s1.length() == 0)
return s2.length() == 0;
if (s2.length() == 0)
return true;
if (s1.length() < s2.length())
return false;
Map<Character, Integer> window = new HashMap<>();
Map<Character, Integer> needs = new HashMap<>();
for (int i = 0; i < s2.length(); i++) {
if (needs.containsKey(s2.charAt(i))) {
needs.put(s2.charAt(i), needs.get(s2.charAt(i)) + 1);
} else {
needs.put(s2.charAt(i), 1);
}
}
int count = needs.size();//符合的大小数目
int left = 0, right = 0;
while (right < s1.length()) {
//先处理右指针
char curr = s1.charAt(right);
if (needs.containsKey(curr)) {
if (window.containsKey(curr)) {
window.put(curr, window.get(curr) + 1);
} else {
window.put(curr, 1);
}
if (window.get(curr).equals(needs.get(curr))) {
count--;
}
}
right++;
//再处理左指针
while (right - left > s2.length()) {
char l = s1.charAt(left);
if (window.containsKey(l)) {
//左指针在处理前是满足相等的，要把这个数组加回去
if (window.get(l).equals(needs.get(l))) {
count++;
}
window.put(l, window.get(l) - 1);
}
left++;
}
//左右指针处理完了，此时count=0，返回true
if (count == 0)
return true;
}
return false;
}
Q：给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:
输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
示例 2:
输入:
s: "abab" p: "ab"
输出:
[0, 1, 2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
A：
public List<Integer> findAnagrams(String s, String p) {
List<Integer> array = new ArrayList<>();
if (s.length() == 0 || p.length() == 0 || s.length() < p.length())
return array;
int left = 0, right = 0;
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (int i = 0; i < p.length(); i++) {
if (need.containsKey(p.charAt(i))) {
need.put(p.charAt(i), need.get(p.charAt(i)) + 1);
} else {
need.put(p.charAt(i), 1);
}
}
int count = need.size();
while(right < s.length()){
char r = s.charAt(right);
if(need.containsKey(r)){
if(window.containsKey(r)){
window.put(r,window.get(r)+1);
}else{
window.put(r,1);
}
if(window.get(r).equals(need.get(r))){
count--;
}
}
right++;
while(right-left>p.length()){
char l = s.charAt(left);
if(window.containsKey(l)){
if(window.get(l).equals(need.get(l))){
count++;
}
window.put(l, window.get(l) - 1);
}
left++;
}
if(count == 0){
array.add(left);
}
}
return array;
}