题目链接
这个是滑动窗口问题比较难的了,不太好想。
我借鉴了这个大佬的思想,用更容易理解的方式实现了一下,可能时间复杂度有点提高。
代码搭配详解使用:题解
这个是我的题解
class Solution {
public String minWindow(String s, String t) {
String res = "";
HashMap<Character, Integer> map = new HashMap<>();
int start = 0, end = 0;
//把字符串t的字符出现的次数对应到哈希表里面
for (int i = 0; i < t.length(); i++) {
int value = map.getOrDefault(t.charAt(i), 0);
map.put(t.charAt(i), value + 1);
}
//遍历循环体,在end走到尽头时退出
for (; end < s.length(); end++) {
//当匹配到t里面的字符时
if (map.containsKey(s.charAt(end))) {
int value = map.get(s.charAt(end));
map.put(s.charAt(end), value - 1);
//哨兵,判断当前是否满足覆盖子串的条件
boolean flag = true;
//只有当所有value都不大于0时,满足条件
for (int i : map.values()) {
if (i > 0) {
flag = false;
break;
}
}
//满足条件,跳过无用字符,找到关键字符
while (flag) {
if (map.containsKey(s.charAt(start))) {
int v = map.get(s.charAt(start));
//点睛之笔,加一的这个操作没经验很难写出来的
map.put(s.charAt(start), v + 1);
for (int i : map.values()) {
if (i > 0) {
flag = false;
break;
}
}
//找到关键字符后,判断长度,取最小
if (!flag) {
if (res.length() == 0) {
res = s.substring(start, end + 1);
} else {
res = end - start + 1 < res.length() ? s.substring(start, end + 1) : res;
}
}
}
start++;
}
}
}
return res;
}
}
这个是本地IDEA上运行的代码,可以直接跑,调试。
import java.util.*;
public class Main {
public static String minWindow(String s, String t) {
String res = "";
HashMap<Character, Integer> map = new HashMap<>();
int start = 0, end = 0;
//把字符串t的字符出现的次数对应到哈希表里面
for (int i = 0; i < t.length(); i++) {
int value = map.getOrDefault(t.charAt(i), 0);
map.put(t.charAt(i), value + 1);
}
//遍历循环体,在end走到尽头时退出
for (; end < s.length(); end++) {
//当匹配到t里面的字符时
if (map.containsKey(s.charAt(end))) {
int value = map.get(s.charAt(end));
map.put(s.charAt(end), value - 1);
//哨兵,判断当前是否满足覆盖子串的条件
boolean flag = true;
//只有当所有value都不大于0时,满足条件
for (int i : map.values()) {
if (i > 0) {
flag = false;
break;
}
}
//满足条件,跳过无用字符,找到关键字符
while (flag) {
if (map.containsKey(s.charAt(start))) {
int v = map.get(s.charAt(start));
//点睛之笔,加一的这个操作没经验很难写出来的
map.put(s.charAt(start), v + 1);
for (int i : map.values()) {
if (i > 0) {
flag = false;
break;
}
}
//找到关键字符后,判断长度,取最小
if (!flag) {
if (res.length() == 0) {
res = s.substring(start, end + 1);
} else {
res = end - start + 1 < res.length() ? s.substring(start, end + 1) : res;
}
}
}
start++;
}
}
}
return res;
}
public static void main(String[] args) {
System.out.println(minWindow("ADOBECODEBANC", "ABC"));
}
}