题目描述
思路：滑动窗口模板
- 需要维护的变量：
// 1. 用于存放结果
List<Integer> res = new ArrayList<>();
// 2. 定义需要维护的变量:根据题意可知是一个哈希表
Map<Character, Integer> map = new HashMap<>();
Map<Character, Integer> hashmap_p = new HashMap<>();
for (char ch : p.toCharArray()) {
hashmap_p.put(ch, hashmap_p.getOrDefault(ch, 0) + 1);
}
- 窗口长度为固定，所以用if：
if (end >= p.length() - 1) {
// 或者 if (end - start + 1 == p.length()) {}
char startChar = s.charAt(start);
map.put(startChar, map.get(startChar) - 1);
if (map.get(startChar) == 0) {
map.remove(startChar);
}
start ++;
}
类似LeetCode643. 子数组最大平均数I
方法一：滑动窗口
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// 1. 用于存放结果
List<Integer> res = new ArrayList<>();
// 2. 定义需要维护的变量:根据题意可知是一个哈希表
Map<Character, Integer> map = new HashMap<>();
Map<Character, Integer> hashmap_p = new HashMap<>();
for (char ch : p.toCharArray()) {
hashmap_p.put(ch, hashmap_p.getOrDefault(ch, 0) + 1);
}
// 3. 定义窗口区间范围
int start = 0;
for (int end = 0; end < s.length(); end ++) {
// 4. 更新需要维护的变量
char currentChar = s.charAt(end);
map.put(currentChar, map.getOrDefault(currentChar, 0) + 1);
if (map.equals(hashmap_p)) {
res.add(start);
}
// 5. 由题意知:窗口固定用if
if (end >= p.length() - 1) {
char startChar = s.charAt(start);
map.put(startChar, map.get(startChar) - 1);
if (map.get(startChar) == 0) {
map.remove(startChar);
}
start ++;
}
}
return res;
}
}
方法二：跟方法一在最后一个if中处理不同
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// 1. 用于存放结果
List<Integer> res = new ArrayList<>();
// 2. 定义需要维护的变量:根据题意可知是一个哈希表
Map<Character, Integer> map = new HashMap<>();
Map<Character, Integer> hashmap_p = new HashMap<>();
for (char ch : p.toCharArray()) {
hashmap_p.put(ch, hashmap_p.getOrDefault(ch, 0) + 1);
}
// 3. 定义窗口区间范围
int start = 0;
for (int end = 0; end < s.length(); end ++) {
// 4. 更新需要维护的变量
char currentChar = s.charAt(end);
map.put(currentChar, map.getOrDefault(currentChar, 0) + 1);
if (map.equals(hashmap_p)) {
res.add(start);
}
// 5. 由题意知:窗口固定用if
if (end - start + 1 == p.length()) {
char startChar = s.charAt(start);
map.put(startChar, map.get(startChar) - 1);
if (map.get(startChar) == 0) {
map.remove(startChar);
}
start ++;
}
}
return res;
}
}