力扣热门100题之最小覆盖子串

核心解法滑动窗口 哈希表思路4 步走用数组 / 哈希表统计 t 中字符的出现次数用左右指针形成滑动窗口右指针一直右移直到窗口包含 t 所有字符满足条件后左指针尽量右移缩小窗口记录最小窗口1. 两个计数数组用数组比 HashMap 更快128 覆盖所有 ASCII 字符int[] need[128]; // 记录 t 里每个字符需要多少个 int[] window[128]; // 记录当前窗口里每个字符有多少个2. 统计 t 字符数量比如 t“ABC”need [A]1, need [B]1, need [C]1for (char c : t.toCharArray()) need[c];3. 右指针扩张窗口右指针一直走遇到 t 需要的字符就加入窗口当窗口字符数 需要的数量时validwhile (valid t.length()) { 更新最小窗口 左指针右移 如果移出的是需要的字符可能导致 valid-- }4. 左指针收缩窗口最关键valid t.length()→窗口已经包含 t 所有字符这时尽量移动左指针缩小窗口寻找更短的满足条件的窗口while (valid t.length()) { 更新最小窗口 左指针右移 如果移出的是需要的字符可能导致 valid-- }5. 最后返回结果return minLen 无穷大 ? : s.substring(start, startminLen)核心变量总结need[]t 需要的字符数量window[]当前窗口字符数量valid窗口中已经满足数量要求的字符种类数valid t.length()→窗口满足条件完整代码实现class Solution { public String minWindow(String s, String t) { // 用于统计字符串 t 中每个字符需要出现的次数 int[] need new int[128]; // 用于统计当前滑动窗口内各字符的数量 int[] window new int[128]; // 记录 t 中有多少种【不同的字符】比如 taa → 只有1种 int needUnique 0; // 第一步统计 t 中所有字符的需求 for (char c : t.toCharArray()) { // 第一次遇到这个字符才增加种类数 if (need[c] 0) { needUnique; } need[c]; } // 滑动窗口左右指针 int left 0, right 0; // 记录窗口内已经满足数量要求的【字符种类数】 int valid 0; // 记录最小窗口的起始位置和长度 int start 0; int minLen Integer.MAX_VALUE; // 第二步移动右指针扩展窗口 while (right s.length()) { // 当前要加入窗口的字符 char c s.charAt(right); right; // 如果这个字符是 t 中需要的字符 if (need[c] 0) { // 窗口中该字符数量 1 window[c]; // 如果当前字符的数量【刚好达到需求】 // 说明这一种字符凑齐了valid 1 if (window[c] need[c]) { valid; } } // 第三步当窗口满足条件时所有字符种类都凑齐了 // 开始移动左指针缩小窗口寻找更短的子串 while (valid needUnique) { // 更新最小窗口如果当前窗口更小就记录下来 if (right - left minLen) { start left; minLen right - left; } // 要移出窗口的字符 char d s.charAt(left); left; // 如果移出的字符是 t 中需要的字符 if (need[d] 0) { // 如果移出前该字符数量刚好满足需求 // 那么移出后就不满足了 → valid -1 if (window[d] need[d]) { valid--; } // 窗口中该字符数量 -1真正移出 window[d]--; } } } // 最后如果没有找到合法窗口返回空字符串 // 否则返回最小窗口子串 return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen); } }