题目链接
这个是滑动窗口问题比较难的了,不太好想。
我借鉴了这个大佬的思想,用更容易理解的方式实现了一下,可能时间复杂度有点提高。
代码搭配详解使用:题解
这个是我的题解
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"));}
}