京公网安备11010502063487号给定字符串 s 和 t，在 s 里找出最短的连续子串，使它包含 t 中所有的字符（包括重复的：t 里有两个 a，子串里就至少要有两个 a），找不到返回空串。暴力做法是枚举所有子串再检查，代价很高。标准做法是滑动窗口：右边界向右扩张，直到窗口覆盖了 t；然后尽可能地收缩左边界，同时记录最短的合法窗口；收缩到不再覆盖了，再继续扩张右边界。每个字符最多进出窗口各一次，所以是线性的。本文用真实数据展示"用集合代替计数"会错多少，实测滑动窗口与暴力枚举的耗时，给出五种语言的实现，并把窗口的扩张和收缩做成分步演示。
完整题目见官方页面（链接在文末）。基准解按窗口长度从小到大、同一长度里从左到右，逐个检查窗口是否覆盖 t（用计数器相减判断），找到的第一个就是最短的，并且是最靠左的最短窗口；滑动窗口的解也只在窗口严格变短时才更新，所以同样返回最靠左的最短窗口，两者可以逐字符比较。一共 14 组用例，覆盖：官方三个示例、t 比 s 长、t 里有重复字符、s 里没有 t 的字符、整个 s 就是答案：
输入 ["ADOBECODEBANC","ABC"] 输出 "BANC" 输入 ["a","a"] 输出 "a" 输入 ["a","aa"] 输出 "" 输入 ["ab","b"] 输出 "b" 输入 ["aa","aa"] 输出 "aa" 输入 ["abc","cba"] 输出 "abc"
如果只检查"t 里的每一种字符都出现过"，而不数个数，就会把 t = "aa" 当成只要一个 a 就够了。下面是用集合判断覆盖的写法与 solve 的真实结果：
# 用集合代替计数的写法（忽略 t 里重复的字符） s='ADOBECODEBANC', t='ABC': 用集合 -> 'BANC' solve -> 'BANC' s='aa', t='aa': 用集合 -> 'a' solve -> 'aa' s='abcabdebac', t='cda': 用集合 -> 'cabd' solve -> 'cabd' s='baab', t='aab': 用集合 -> 'ba' solve -> 'baa' s='aabbcc', t='abcc': 用集合 -> 'abbc' solve -> 'abbcc' 随机 20000 组：该写法与正确答案不同的有 7530 组（37.6%）
s = "aa"、t = "aa"：用集合的写法返回 "a"（只有一个 a），而 t 要求两个，正确答案是 "aa"；baab 与 aab 同理。第一行（官方示例 ADOBECODEBANC/ABC）和第三行（abcabdebac/cda）两种写法碰巧一致，因为 t 里没有重复字符。在随机的 20000 组数据里（字母只有 a、b、c，重复很多），用集合的写法出错的有 7530 组，占 37.6%。
need[ch] 表示窗口里还缺几个 ch，初始时是 t 里 ch 出现的次数，窗口里多出来的字符会让它变成负数；missing 是还缺的字符总数，为 0 说明窗口覆盖了 t。右边界 right 每读入一个字符：如果这个字符还缺（need > 0），missing 减一；need 减一。然后当 missing == 0（窗口覆盖了 t）：如果窗口比之前记录的更短，就记录；再把左边界的字符移出：need 加一，如果它变成了正数（说明移出的是必需的字符），missing 加一；left 右移。循环直到 missing 不再是 0。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；Java、Go、JavaScript、C++ 用长度 128 的数组做计数（题目的字符是英文字母）。
Python · 解法代码def solve(s, t): need = {} for ch in t: need[ch] = need.get(ch, 0) + 1 # need[ch]：还缺几个 ch（可以变成负数，表示窗口里多了几个） missing = len(t) # 还缺的字符总数；为 0 说明窗口已经覆盖了 t best_l, best_len = 0, len(s) + 1 left = 0 for right, ch in enumerate(s): # 右边界向右扩张 if need.get(ch, 0) > 0: missing -= 1 need[ch] = need.get(ch, 0) - 1 while missing == 0: # 窗口已经覆盖 t：尽量收缩左边界，找最短的 if right - left + 1 < best_len: best_l, best_len = left, right - left + 1 lc = s[left] need[lc] += 1 if need[lc] > 0: # 移出的是必需的字符：又缺了 missing += 1 left += 1 return "" if best_len > len(s) else s[best_l:best_l + best_len]
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON ["ADOBECODEBANC","ABC"] → "BANC" ["a","a"] → "a" ["a","aa"] → "" ["ab","b"] → "b" ["aa","aa"] → "aa" ["abc","cba"] → "abc"
Java · 解法代码class Solution { public String minWindow(String s, String t) { int[] need = new int[128]; // need[ch]：还缺几个 ch（可以变成负数，表示窗口里多了几个） for (char ch : t.toCharArray()) need[ch]++; int missing = t.length(); // 还缺的字符总数；为 0 说明窗口已经覆盖了 t int bestL = 0, bestLen = s.length() + 1, left = 0; for (int right = 0; right < s.length(); right++) { // 右边界向右扩张 char ch = s.charAt(right); if (need[ch] > 0) missing--; need[ch]--; while (missing == 0) { // 窗口已经覆盖 t：尽量收缩左边界，找最短的 if (right - left + 1 < bestLen) { bestL = left; bestLen = right - left + 1; } char lc = s.charAt(left); need[lc]++; if (need[lc] > 0) missing++; // 移出的是必需的字符：又缺了 left++; } } return bestLen > s.length() ? "" : s.substring(bestL, bestL + bestLen); } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl ["ADOBECODEBANC","ABC"] → "BANC" ["a","a"] → "a" ["a","aa"] → "" ["ab","b"] → "b" ["aa","aa"] → "aa" ["abc","cba"] → "abc"
Go · 解法代码func minWindow(s string, t string) string { var need [128]int // need[ch]：还缺几个 ch（可以变成负数，表示窗口里多了几个） for i := 0; i < len(t); i++ { need[t[i]]++ } missing := len(t) // 还缺的字符总数；为 0 说明窗口已经覆盖了 t bestL, bestLen, left := 0, len(s)+1, 0 for right := 0; right < len(s); right++ { // 右边界向右扩张 ch := s[right] if need[ch] > 0 { missing-- } need[ch]-- for missing == 0 { // 窗口已经覆盖 t：尽量收缩左边界，找最短的 if right-left+1 < bestLen { bestL, bestLen = left, right-left+1 } lc := s[left] need[lc]++ if need[lc] > 0 { // 移出的是必需的字符：又缺了 missing++ } left++ } } if bestLen > len(s) { return "" } return s[bestL : bestL+bestLen] }
$ go build -o bin . && ./bin < cases.jsonl ["ADOBECODEBANC","ABC"] → "BANC" ["a","a"] → "a" ["a","aa"] → "" ["ab","b"] → "b" ["aa","aa"] → "aa" ["abc","cba"] → "abc"
JavaScript · 解法代码function minWindow(s, t) { const need = new Array(128).fill(0); // need[ch]：还缺几个 ch（可以变成负数，表示窗口里多了几个） for (const ch of t) need[ch.charCodeAt(0)]++; let missing = t.length; // 还缺的字符总数；为 0 说明窗口已经覆盖了 t let bestL = 0, bestLen = s.length + 1, left = 0; for (let right = 0; right < s.length; right++) { // 右边界向右扩张 const c = s.charCodeAt(right); if (need[c] > 0) missing--; need[c]--; while (missing === 0) { // 窗口已经覆盖 t：尽量收缩左边界，找最短的 if (right - left + 1 < bestLen) { bestL = left; bestLen = right - left + 1; } const lc = s.charCodeAt(left); need[lc]++; if (need[lc] > 0) missing++; // 移出的是必需的字符：又缺了 left++; } } return bestLen > s.length ? "" : s.substring(bestL, bestL + bestLen); }
$ node run.js < cases.jsonl ["ADOBECODEBANC","ABC"] → "BANC" ["a","a"] → "a" ["a","aa"] → "" ["ab","b"] → "b" ["aa","aa"] → "aa" ["abc","cba"] → "abc"
C++ · 解法代码#include <string> #include <vector> using namespace std; class Solution { public: string minWindow(string s, string t) { vector<int> need(128, 0); // need[ch]：还缺几个 ch（可以变成负数，表示窗口里多了几个） for (char ch : t) need[ch]++; int missing = t.size(); // 还缺的字符总数；为 0 说明窗口已经覆盖了 t int bestL = 0, bestLen = (int)s.size() + 1, left = 0; for (int right = 0; right < (int)s.size(); right++) { // 右边界向右扩张 char ch = s[right]; if (need[ch] > 0) missing--; need[ch]--; while (missing == 0) { // 窗口已经覆盖 t：尽量收缩左边界，找最短的 if (right - left + 1 < bestLen) { bestL = left; bestLen = right - left + 1; } char lc = s[left]; need[lc]++; if (need[lc] > 0) missing++; // 移出的是必需的字符：又缺了 left++; } } return bestLen > (int)s.size() ? "" : s.substr(bestL, bestLen); } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl ["ADOBECODEBANC","ABC"] → "BANC" ["a","a"] → "a" ["a","aa"] → "" ["ab","b"] → "b" ["aa","aa"] → "aa" ["abc","cba"] → "abc"
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
构造对暴力解最不利的数据：s 是一个 a、中间很多个 b、一个 c，t 是 ac，答案是整个 s，暴力解要把所有更短的窗口都试一遍。滑动窗口只需扫描一遍。每个规模取三次中最快的一次：
s 的长度 n（s = a + n-2 个 b + c，t = ac：答案是整个 s，暴力解要试遍所有更短的窗口） | 暴力解 | 本文解法
100 | 9.652 ms | 0.007 ms
300 | 142.712 ms | 0.019 ms
1000 | （未测，太慢） | 0.066 ms
100000 | （未测，太慢） | 6.733 ms暴力解从 100 到 300（3 倍）耗时增长约 14.8 倍，接近平方以上（每个窗口的检查本身也是线性的，所以理论上接近立方）；滑动窗口从 100 到 1000 增长约 9.4 倍，从 1000 到 10 万（100 倍）增长约 102 倍，是线性。n = 300 时暴力解 142.7ms，滑动窗口 0.019ms，约 7500 倍。暴力解在 n = 1000 及以上没有再测。
Python 版本另外和暴力枚举做了随机对拍：s 长 1 到 12，t 长 1 到 4，字母只有 a、b、c（重复字母很多，最容易暴露计数的错误）：
随机对拍 20000 组（s 长 1 到 12、t 长 1 到 4，字母取自 a、b、c（重复字母很多）；两种做法都返回最左边的最短窗口，所以逐字符比较），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 s = "ADOBECODEBANC"、t = "ABC"。右边界一直向右扩张，读到 C（下标 5）时窗口 ADOBEC 第一次覆盖了 A、B、C，记录；然后收缩左边界，移出 A 后窗口就不再覆盖了，继续扩张……最终得到最短的覆盖窗口 BANC。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。