题目概览给定两个字符串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由英文字母组成来源76. 最小覆盖子串 - 力扣LeetCode解题分析方法滑动窗口求最小子串其实就是看每个满足条件的滑动窗口长度最小我们可以定义 i 和 j 一同指向第一个元素当 i 和 j 范围内元素不满足条件往右边移动若满足条件则得到一个初步的子串由于 i 指向的元素不能不在 t 中因此还要移动 i 直到不满足条件这样就可以得到一个可能是最小的子串。然后继续移动 j重复步骤即可。看是否满足条件可以定义一个哈希map来存储 t 的字母和出现次数然后比较当前子串字母和次数是否对的上即可。由于这里的字母都是大小写英文字母我们也可以用 128 的数组来实现。时间复杂度O(n)空间复杂度O(k)class Solution { public String minWindow(String s, String t) { int[] mapping new int[128]; char[] cs s.toCharArray(); char[] ct t.toCharArray(); for (char c: ct) { mapping[c]; } int tLen ct.length, sLen cs.length; int i 0, j 0; int[] temp new int[128]; int minI 0, minJ sLen; while(i sLen j sLen) { temp[cs[j]]; while(isCovered(temp, mapping)) { if (j - i minJ - minI) { minI i; minJ j; } temp[cs[i]]--; i; } j; } return minJ sLen ? : s.substring(minI, minJ 1); } public boolean isCovered(int[] cs, int[] ct) { for (int i A; i Z; i) { if (cs[i] ct[i]) { return false; } } for (int i a; i z; i) { if (cs[i] ct[i]) { return false; } } return true; } }