一、滑动窗口题型模板
/*
* 滑动窗口类型： 模板
*/
public List<Integer> slideWindowMode(String s, String t) {
// 1 根据题目返回类型定义数据结构
ArrayList<Integer> result = new ArrayList<>();
if(t.length()> s.length())
return result;
// 2 新建Map， Key=字符，value=频率
HashMap<Character, Integer> map = new HashMap<>();
for(char c: t.toCharArray())
map.put(c, map.getOrDefault(c, 0) + 1); // 3 定义变量
int counter = map.size(); // 目标字符串中的不同字符种类
int begin = 0, end = 0; // 窗口起始、结束点
int len = Integer.MAX_VALUE; // 4 源字符串开始遍历
while(end < s.length()) {
// 5 统计每个字符
char c = s.charAt(end);
if(map.containsKey(c)) {
map.put(c, map.get(c) - 1);
if(map.get(c) == 0)
counter--;
}
end++; // 6 符合情况！begin~end 之间包含 t 的所有字符
while(counter == 0) { // 此时 Map 的 value 全部 <= 0
char tmpc = s.charAt(begin);
if(map.containsKey(tmpc)) {
map.put(tmpc, map.get(tmpc) + 1);
if(map.get(tmpc) > 0)
counter++;
} // 7 do sth begin++;
}
}
// 8
return result;
}
二、LeetCode 中 几个滑动窗口套用模板实现
1、 76. Minimum Window Substring
https://leetcode.com/problems/minimum-window-substring/description/
public String minWindow(String s, String t) {
if(t.length()> s.length()) return "";
HashMap<Character, Integer> map = new HashMap<>();
for(char c: t.toCharArray())
map.put(c, map.getOrDefault(c, 0) + 1);
int counter = map.size(); // 目标字符串中的不同字符种类
int begin = 0, end = 0; // 窗口起始、结束点
int len = Integer.MAX_VALUE;
int head = 0;
while(end < s.length()) {
char c = s.charAt(end);
if( map.containsKey(c) ) {
map.put(c, map.get(c) - 1);
if(map.get(c) == 0)
counter--;
}
end++;
while(counter == 0) { // 此时 Map 的 value 全部 <= 0
char tmpc = s.charAt(begin);
if( map.containsKey(tmpc) ) {
map.put(tmpc, map.get(tmpc) + 1);
if(map.get(tmpc) > 0)
counter++;
}
//----------
if(end - begin < len) {
len = end - begin;
head = begin;
}
//----------
begin++;
}
}
if(len == Integer.MAX_VALUE )
return "";
return s.substring(head, head + len);
}
2、3 Longest Substring Without Repeating Characters
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
/*
* 2、 Longest Substring Without Repeating Characters
*/
public int lengthOfLongestSubstring(String s) { HashMap<Character, Integer> map = new HashMap<>();
int begin = 0; // 窗口起始、结束点
int max = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(map.containsKey(c)) {
max = Math.max(max, i - begin);
begin = Math.max(begin, map.get(c) + 1);
map.put(c, i);
}
else {
map.put(c, i);
}
}
max = Math.max(s.length() - begin, max);
return max;
}
3、438. Find All Anagrams in a String
https://leetcode.com/problems/find-all-anagrams-in-a-string/description/
public List<Integer> findAnagrams(String s, String t) {
ArrayList<Integer> result = new ArrayList<>();
if(s.length() < t.length())
return result;
HashMap<Character, Integer> map = new HashMap<>();
for(char c: t.toCharArray())
map.put(c, map.getOrDefault(c, 0) + 1);
int counter = map.size();
int begin = 0, end = 0;
// int head = 0;
// int len = Integer.MAX_VALUE;
while(end < s.length()) {
char c = s.charAt(end);
if( map.containsKey(c) ) {
map.put(c, map.get(c) - 1);
if(map.get(c) == 0)
counter--;
}
end++;
while(counter == 0) {
char tmpc = s.charAt(begin);
if( map.containsKey(tmpc) ) {
map.put(tmpc, map.get(tmpc) + 1);
if(map.get(tmpc) > 0)
counter++;
}
//--------
if(end - begin == t.length())
result.add(begin);
//--------
begin++;
}
}
return result;
}