滑动窗口
包含特定元素的子串（要匹配到的目标），或最长[这个好像没啥意思]、或最短、或等长
思考：（暂时感受）
1）什么时候扩充窗口——串没走完就得扩呀；
2）窗口扩充后要更新哪些东西——窗口包括的内容，毕竟新来人了，东西多了；
3）什么时候缩小窗口——得看目标条件是啥了，最短的情况吧只要目标条件够了就得收缩，等长的情况吧等长就得缩噻；
4）窗口缩小后要更新哪些东西——窗口包括的内容；
5）什么时候更新结果——收缩的时候，还是一轮结束的时候。
1. 最小覆盖子串 76 简单
class Solution {
public String minWindow(String s, String t) {
// 两个Map记录目标字符以及窗口包含的字符
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
// 填充目标字符的Map
for (char c: t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
// 设置左右指针，区间范围是左闭右开，所以刚开始区间内没有元素
int left = 0;
int right = 0;
int valid = 0; // 窗口中满足需要的字符个数
// 记录最小覆盖子串的起始索引和长度
int start = 0;
int len = Integer.MAX_VALUE;
// 扩大窗口至覆盖子串
while (right < s.length()) {
char c = s.charAt(right);
// 扩大窗口
right ++;
// 对窗口内的数据进行更新
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
// 窗口内某个字符满足个数要求了
valid ++;
}
}
// 缩小窗口仍覆盖子串
while (valid == need.size()) {
// 更新最小覆盖子串
if (right - left < len) {
start = left;
len = right - left;
}
// 缩小窗口
char d = s.charAt(left);
left ++;
// 对窗口内的数据进行更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid --;
}
window.put(d, window.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
2. 字符串的排列 567 中等
class Solution {
public boolean checkInclusion(String s1, String s2) {
// 思路：缩到最小覆盖，长度如果与s1相等，说明s1的排列之一是s2的子串
// Map记录数量
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
// 填充need
for (char c : s1.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
// 滑动窗口
int left = 0;
int right = 0;
// int start = 0;
// int len = Integer.MAX_VALUE;
int valid = 0;
while (right < s2.length()) {
char c = s2.charAt(right);
// 扩大窗口
right ++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid ++;
}
}
while (right - left >= s1.length()) {
// while (valid == need.size()) {
// if (right - left < len) {
// start = left;
// len = right - left;
// }
// 判断是否找到了合适的子串
if (valid == need.size()) {
return true;
}
char d = s2.charAt(left);
left ++;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid --;
}
window.put(d, window.get(d) - 1);
}
}
// if (len == s1.length()) {
// return true;
// }
}
return false;
}
}
3. 找到字符串中所有字母异位词 438 中等
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// 存放结果
List<Integer> result = new ArrayList<>();
// 存放窗口元素
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : p.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
// 滑动窗口的左右指针
int left = 0;
int right = 0;
int valid = 0;
while (right < s.length()) {
char c = s.charAt(right);
// 扩大窗口
right ++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (need.get(c).equals(window.get(c))) {
valid ++;
}
}
while (right - left >= p.length()) {
if (valid == need.size()) {
result.add(left);
// // window和valid要清空
// window.clear();
// valid = 0;
}
char d = s.charAt(left);
left ++;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid --;
}
window.put(d, window.get(d) - 1);
}
}
}
return result;
}
}
4. 无重复字符的最长子串 3 中等
class Solution {
public int lengthOfLongestSubstring(String s) {
// 结果
int result = 0;
// 滑动窗口：重要的是如果map中键的值超过2，那就说明需要缩小窗口了
Map<Character, Integer> window = new HashMap<>();
int left = 0;
int right = 0;
while (right < s.length()) {
char c = s.charAt(right);
right ++;
window.put(c, window.getOrDefault(c, 0) + 1);
while (window.get(c) > 1) {
char d = s.charAt(left);
left ++;
window.put(d, window.get(d) - 1);
}
// 更新答案
result = Math.max(result, right - left);
}
return result;
}
}
【未完待续……】
