目录一、题目解析二、讲解算法原理解法一暴力枚举 哈希表解法二滑动窗口 哈希表优化判断条件三、代码实现大家好今天我们来攻克 LeetCode 上的一道经典难题——76. 最小覆盖子串。这道题是滑动窗口算法的典型应用结合了哈希表来优化判断过程。一、题目解析题目​ 给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串则返回空字符串。注意对于t中重复字符我们寻找的子串中该字符数量必须不少于t中该字符数量。如果s中存在这样的子串我们保证它是唯一的答案。示例 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的子串中因此没有符合条件的子子串返回空字符串。二、讲解算法原理解法一暴力枚举 哈希表解法二滑动窗口 哈希表这是本题的最优解。核心思想是维护一个窗口[left, right]通过移动左右指针来寻找最小覆盖子串。核心逻辑right 右移​ 不断扩大窗口直到窗口包含了t中的所有字符。left 右移​ 在满足覆盖条件的前提下尝试缩小窗口左边界以找到最小长度。优化判断条件为了优化每次判断窗口是否覆盖t的时间复杂度我们可以引入一个变量count。思路​ 使用变量count标记有效字符的种类。进窗口​ 当hash2[in] hash1[in]时count。出窗口​ 当hash2[out] hash1[out]时count--。判断条件​ 当count hash1.size()时说明窗口已覆盖t。三、代码实现class Solution { public String minWindow(String ss, String tt) { char[] s ss.toCharArray(); char[] t tt.toCharArray(); int[] hash1 new int[128]; // 统计字符串 t 中字符的频次 int kinds 0; // 字符串 t 中有多少种字符 for(char ch : t) { if(hash1[ch] 0) kinds; } int[] hash2 new int[128]; // 统计窗口中字符的频次 int minlen Integer.MAX_VALUE, begin -1; for(int left 0, right 0, count 0; right s.length; right) { char in s[right]; if(hash2[in] hash1[in]) count; // 进窗口 维护 count while(kinds count) // 判断 { // 更新结果 if(right - left 1 minlen) { begin left; minlen right - left 1; } char out s[left]; if(hash2[out]-- hash1[out]) count--; // 出窗口 维护 count } } if(begin -1) return new String(); else return ss.substring(begin, begin minlen); } }