题目给定两个字符串s和t长度分别是m和n返回 s 中的最短窗口 子串使得该子串包含t中的每一个字符包括重复字符。如果没有这样的子串返回空字符串。测试用例保证答案唯一。示例 1输入s ADOBECODEBANC, t ABC输出BANC解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。示例 2输入s a, t a输出a解释整个字符串 s 是最小覆盖子串。示例 3:输入:s a, t aa输出:解释:t 中两个字符 a 均应包含在 s 的子串中 因此没有符合条件的子字符串返回空字符串。提示m s.lengthn t.length1 m, n 105s和t由英文字母组成进阶你能设计一个在O(m n)时间内解决此问题的算法吗题解class Solution { public String minWindow(String s, String t) { // 哈希值存储大小写字母出现的次数 int[] need new int[128]; // t需要的字符计数 int[] window new int[128]; // 当前窗口内字符计数 for(char ch : t.toCharArray()){ need[ch]; } int left 0; int valid 0; // valid窗口中满足 need条件的字符种类数量 int start 0; // 答案子串起始下标 int minLen Integer.MAX_VALUE; // 答案子串长度 for(int right 0; right s.length(); right){ char rCh s.charAt(right); if(need[rCh] 0){ window[rCh]; // 当前字符数量已经达标有效种类1 if(window[rCh] need[rCh]){ valid; } } // valid t中字符种类数窗口已经完全覆盖t开始收缩左边界 while(valid countTChar(need)){ // 更新最小窗口 int curLen right - left 1; if(curLen minLen){ minLen curLen; start left; } // 移出左边字符 char lCh s.charAt(left); if(need[lCh] 0){ // 如果这个字符刚好等于需要数量删掉之后就不满足了valid减少 if(window[lCh] need[lCh]){ valid--; } window[lCh]--; } left; } } // minLen没变化说明没有找到 return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen); } // 统计t一共有多少种字符need数组0 private int countTChar(int[] need){ int cnt 0; for(int i 0; i 128; i){ if(need[i] 0) cnt; } return cnt; } }