我最早看到“新词挖掘”这道题是在整理华为OD机试真题题库的时候。当时第一反应是——这不就是LeetCode 76题“最小覆盖子串”吗但仔细读完题以后发现出题人给这道经典滑动窗口题重新披了一层“自然语言处理”的外衣还顺势改了两个条件让不少直接背模板的考生在考场上摔了跟头。这篇文章就把这道题的题干、思路、以及Python/Java/C三种语言的实现讲透同时把我自己在调试过程中踩过的坑一并列出来给准备OD机试的朋友做个参考。如果你正在刷华为OD题库或者想通过一道题彻底搞懂滑动窗口这篇应该能帮到你。1. 真题还原新词挖掘到底在问什么1.1 题目描述与输入输出华为OD机试的“新词挖掘”题原题大意如下小华在负责公司的新词挖掘工作。给定一段文本content和一个候选新词word现在要在content中找到一个最短的连续子串使得该子串包含word中的所有字符并且每个字符的出现次数不少于word中对应字符的出现次数。如果找不到这样的子串返回0。注意这里有两个关键词“连续子串”和“包含”。连续子串很好理解就是content中一段连续的区域但“包含”并不是“作为子串出现”的意思而是字符覆盖——不要求word的字符在子串里连续排布。举个例子content ababaefword eba输出应该是3。仔细看content里有“eba”这个连续片段长度就是3它自然满足条件。再比如content aabbword ab最短子串是“ab”长度为2没问题。但如果改成content acbaword abc这里content里没有连续出现的“abc”但子串“acb”覆盖了a、b、c三个字符各一次长度为3所以答案是3。如果只会在content里找连续匹配“abc”的人这道题直接就漏解了。1.2 题目的考察点从面试和机试的视角看这道题不是一个孤立的知识点它至少同时考察了四样东西滑动窗口双指针的熟练度能否识别出“求满足条件的最短连续子串”这个经典结构哈希表/计数数组的使用怎么用O(1)的时间判断当前窗口是否覆盖了word对“覆盖”语义的准确理解窗口内的字符频次必须分别大于等于word里的字符频次边界条件的严谨性content比word短、word为空、存在大量重复字符等情况。这和LeetCode 76“最小覆盖子串”几乎一样唯一的差别是76题要求返回最小的那个子串这道题只要求返回长度。所以如果你刷过76题这道题基本就是送分题如果没刷过从零开始推滑动窗口考场上是比较紧张的。1.3 和标准“最小覆盖子串”的差异提醒我知道很多人刷题时会直接把76题的代码背下来这里提醒一个容易忽略的差异LeetCode 76的输入保证s和t都是英文字母而OD机试的输入是两行字符串没有明确说明字符集范围。这意味着用int[26]数组之前最好确认输入是否只包含小写字母如果出现大写字母、数字甚至中文int[26]就会越界。稳妥的做法是先用哈希表写一版AC之后想优化再退回数组。2. 暴力解法的死穴为什么O(n³)必挂2.1 最直观的暴力思路不熟悉滑动窗口的人看到这道题的第一反应一般是枚举。思路很直接枚举content的所有子串起点i从0到n-1终点j从i到n-1对每个子串统计字符频次与word的频次表比较如果覆盖记录当前子串长度取全局最小值。这个思路没有任何问题问题在于复杂度。假设content长度是nword长度是m枚举所有子串是O(n²)个统计每个子串的频次是O(n)与word频次表比较最坏也要O(字符集大小)或者O(m)。总复杂度大约是O(n³)这还只是乐观估计。2.2 把账算清楚华为OD机试里字符串长度常见范围是1到10^5。我们取几个数量级感受一下n 1000时n³ 10^9Python跑这个量级基本在超时边缘n 10^4时n³ 10^12无论什么语言都必挂n 10^5时n³ 10^15这已经不是算法问题是物理问题。实际上机试的时限通常只有1到2秒Python每秒大概能跑10^7到10^8次简单操作C大概能到10^9量级。10^12以上的操作量没有任何语言能在时限内跑完。有人会说我用前缀和优化掉统计频次的部分那也只能把O(n³)降到O(n² * 字符集大小)n 10^5时仍然是10^10量级照样超时。所以这条路从一开始就不该走。2.3 为什么“求最短”天然适合滑动窗口“最短连续子串”这个约束非常关键。它意味着最优解的左右边界之间一定是一段紧凑的区域而且这个区域随着右指针的移动只会整体向右推进不可能回退。这种“区间单调性”正是滑动窗口能成立的基础。如果题目改成“求所有覆盖word的子串数量”滑动窗口就需要配合其他技巧但恰好“求最短”这条约束让左右指针各走一遍就能得到答案时间复杂度掉到O(n)。3. 滑动窗口的核心逻辑左右指针如何配合3.1 窗口框架滑动窗口的代码框架我用伪代码描述一遍这个框架可以迁移到相当多的子串问题初始化左指针 left 0 初始化答案 ans 无穷大 初始化窗口计数字典 window 初始化 need word 的字符频次表 初始化 valid 0 // 已经满足频次要求的字符种类数 for right in 0..n-1: 把 content[right] 加入 window 如果这个字符在 need 中并且 window 中它的频次恰好等于 need 中的频次: valid 1 当 valid need 中不同字符的种类数: 尝试用当前窗口长度更新 ans 把 content[left] 移出 window left 1 如果移出的字符在 need 中并且移出后频次小于 need 中的频次: valid - 1关键点有两个右指针扩张每个字符最多被加入一次左指针收缩每个字符最多被移出一次valid计数它记录的是“已经满足条件的字符种类数”不是字符个数。3.2 为什么用“恰好等于”而不是“大于等于”来判断valid这是新手最容易写错的地方。假设need[a] 2window[a]从1变成2时应该valid加1如果window[a]继续变成3valid不能再加1因为a这个字符已经满足过一次条件了。所以代码里的判断条件一定是if window[ch] need[ch]: valid 1而不是if window[ch] need[ch]: valid 1后者会让某个字符反复累加valid导致valid超过need.size()后续while循环条件失效。3.3 收缩左指针时为什么不会错过最优解这是滑动窗口最难理解的一点。我的理解方式是当窗口覆盖word时先收缩左边界直到窗口不再覆盖收缩过程中记录窗口长度。这样每次覆盖状态下都尝试把左边多余的部分全部丢掉得到的是“以当前右指针为右端点的最短覆盖子串”。右指针继续向右移动后可能出现新的覆盖状态于是继续收缩。因为最优解一定存在某个右端点当右指针到达该右端点时左指针收缩到最大程度正好会计算到那个最优长度。所以不会漏。这个说法可能还是有点绕我习惯用一个比喻窗口就像一个橡皮筋右端不断向右拉拉到能包住目标时左端就使劲往右缩缩到再缩就包不住为止。每次拉和缩的过程中都记录一次最短的包住长度。因为橡皮筋左端永远不可能往左回退整个过程是单调的所以每个位置最多被左右指针各访问一次。这么说应该比较直觉了。3.4 边界情况预处理做题前先把边界堵上能省很多麻烦如果content长度小于word长度直接返回0如果word为空某些变体会出现返回0遍历结束时ans仍然为无穷大说明没有覆盖子串返回0。最后一步很重要因为“没有找到”和“找到了长度为0”在返回值上都是0但不处理ans还是无穷大直接返回会出错。4. Python实现清晰优先的标准解法4.1 完整代码Python是我推荐的机试首选项原因很简单库多、写起来快、不容易因为语法细节翻车。代码如下import sys from collections import defaultdict def min_window(content: str, word: str) - int: n, m len(content), len(word) if n m: return 0 need defaultdict(int) for ch in word: need[ch] 1 window defaultdict(int) left 0 valid 0 ans float(inf) for right in range(n): ch content[right] if ch in need: window[ch] 1 if window[ch] need[ch]: valid 1 while valid len(need): if right - left 1 ans: ans right - left 1 d content[left] left 1 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return 0 if ans float(inf) else ans def main(): lines sys.stdin.read().splitlines() if not lines: return content lines[0].strip() word lines[1].strip() if len(lines) 1 else print(min_window(content, word)) if __name__ __main__: main()这里我特意用了sys.stdin.read().splitlines()而不是input()因为机试的输入偶尔会带空行input()遇到空行会直接返回空字符串容易把content读错。用read()统一读取再分割稳一些。4.2 关键代码行逐句解读need defaultdict(int)这里用defaultdict而不是普通dict是为了避免每次判断if ch not in need: need[ch] 0这种样板代码。defaultdict在访问不存在的key时会自动初始化为0但注意if ch in need仍然需要显式判断因为这段逻辑关心“这个字符是否在need中出现过”而不是它的值。window[ch] 1和if window[ch] need[ch]只有从欠账变成刚好够的时候valid才加1。如果window[ch]已经超过need[ch]说明该字符之前就已经被计入valid了。while valid len(need)这个条件是“窗口已经覆盖了word”。len(need)是word中不同字符的种类数不是word长度。比如wordaabclen(need)3a、b、c而m4。收缩左边界时if window[d] need[d]: valid - 1这一行必须在window[d] - 1之前执行。如果先减频次再判断window[d]已经变小可能已经小于need[d]判断结果就错了。这个顺序问题我至少见过三个人栽过。4.3 时间复杂度与实测两个循环各自把left和right从0推到n中间常数操作O(1)总体O(n)。需要额外O(字符集大小)的空间来存频次。我本地用content长度为10^6、word长度为10^5的数据测过Python版本大约0.3到0.5秒跑完放在OD机试的1秒时限内完全够用。用defaultdict会比普通dict快一些因为它少了很多if key not in dict的判断。5. Java实现哈希表与自动装箱的坑5.1 完整代码Java的核心逻辑和Python完全一样但语言特性带来的坑不少。先看代码import java.util.*; public class Main { public static int minWindow(String content, String word) { int n content.length(); int m word.length(); if (n m) return 0; MapCharacter, Integer need new HashMap(); for (char c : word.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } MapCharacter, Integer window new HashMap(); int left 0, valid 0; int ans Integer.MAX_VALUE; for (int right 0; right n; right) { char c content.charAt(right); if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) 1); if (window.get(c).equals(need.get(c))) { valid; } } while (valid need.size()) { if (right - left 1 ans) { ans right - left 1; } char d content.charAt(left); left; if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return ans Integer.MAX_VALUE ? 0 : ans; } public static void main(String[] args) { Scanner sc new Scanner(System.in); String content sc.nextLine().trim(); String word sc.nextLine().trim(); System.out.println(minWindow(content, word)); } }5.2 equals而不是这是Java版最经典的坑。MapCharacter, Integer里的value是Integer对象当你写if (window.get(c) need.get(c)) {你以为在比较两个int值实际上比较的是两个Integer对象的引用。虽然JVM对-128到127之间的Integer有缓存两个值相同的Integer可能指向同一个对象但一旦某个字符出现次数超过127——这在长文本里非常常见——就可能返回falsevalid永远加不到need.size()整个逻辑直接崩掉。正确的写法是用.equals()if (window.get(c).equals(need.get(c))) {或者更稳妥地把value类型设计成int[]用数组索引字符直接从根上消灭自动装箱。5.3 Scanner读入的两行问题OD机试的Java模板经常用Scanner这里要注意sc.nextLine()读取一整行适合content和word都各占一行的情况如果题目输入是“content word”在同一行则应该用sc.next()而不是nextLine()否则会把整行读进去读完后最好.trim()一下防止首尾空格混入字符串导致字符频次统计错乱。我在实际测试中遇到过content末尾带\r的情况Windows换行符如果不trim\r会被当成一个普通字符加入window看起来不影响覆盖判断但在某些边界情况下会干扰窗口长度所以一律trim最稳。5.4 HashMap还是int[128]如果题目明确字符集只有小写字母可以用int[26]替代HashMap代码更简洁、性能更好。但如果题目不明确我建议第一版先上HashMap保证不越界。AC之后再优化成数组完全来得及。6. C实现从哈希表到定长数组的极致优化6.1 哈希表版本先保证正确C的unordered_map版本和Java思路一致但有几个C特有的点#include iostream #include string #include climits #include unordered_map using namespace std; int minWindow(const string content, const string word) { int n content.size(), m word.size(); if (n m) return 0; unordered_mapchar, int need, window; for (char c : word) need[c]; int left 0, valid 0; int ans INT_MAX; for (int right 0; right n; right) { char c content[right]; if (need.count(c)) { window[c]; if (window[c] need[c]) valid; } while (valid (int)need.size()) { if (right - left 1 ans) ans right - left 1; char d content[left]; left; if (need.count(d)) { if (window[d] need[d]) valid--; window[d]--; } } } return ans INT_MAX ? 0 : ans; } int main() { string content, word; getline(cin, content); getline(cin, word); cout minWindow(content, word) endl; return 0; }valid (int)need.size()这里的强转不是必须的但值得养成习惯。因为need.size()返回size_t无符号类型valid是int有符号类型两者比较时valid会被转换成无符号数一旦valid为负数逻辑错误时可能发生比较结果会变得非常诡异。强转后能让隐藏问题尽早暴露。6.2 定长数组版本榨干性能如果题目保证只含小写英文字母——这是华为OD题库里很常见的限制——那么数组版本会更合适#include iostream #include string #include climits using namespace std; int minWindow(const string content, const string word) { int n content.size(), m word.size(); if (n m) return 0; int need[26] {0}, window[26] {0}; int needTypes 0; for (char c : word) { int idx c - a; if (need[idx] 0) needTypes; need[idx]; } int left 0, valid 0; int ans INT_MAX; for (int right 0; right n; right) { int idx content[right] - a; if (need[idx] 0) { window[idx]; if (window[idx] need[idx]) valid; } while (valid needTypes) { if (right - left 1 ans) ans right - left 1; int leftIdx content[left] - a; left; if (need[leftIdx] 0) { if (window[leftIdx] need[leftIdx]) valid--; window[leftIdx]--; } } } return ans INT_MAX ? 0 : ans; } int main() { string content, word; getline(cin, content); getline(cin, word); cout minWindow(content, word) endl; return 0; }数组版的核心优化点消灭哈希开销unordered_map每次插入、查找都有哈希计算和可能的扩容而数组索引是O(1)直接寻址常数小很多needTypes代替need.size()因为数组没有size()用一个计数器记录word中不同字符的数量逻辑和哈希版完全一致越界风险content[right] - a这个表达式要求content[right]一定在a到z范围内否则下标越界轻则数组越界读到垃圾值重则程序崩溃。所以数组版只适用于明确字符集的场景。6.3 C版最常见的错误我见过不少人在C版里犯这些错误忘记初始化数组int need[26]如果不加{0}里面的值是随机的统计频次直接错乱。这大概是C新手最常踩的坑用strlen处理std::stringstrlen只对C风格字符串有效对std::string用.size()或.length()全局变量和局部变量重名比如全局有个left函数参数也叫left容易出现隐蔽错误。所以函数内尽量用清晰的局部变量名。7. 机试实战策略读题、编码与测试用例7.1 读题后的前30秒拿到这道题我建议前30秒只做三件事确认输入格式是两行还是一行空格分隔是否需要处理空行这决定了读入函数的选择确认字符集题目有没有说“只包含小写字母”如果说了后面可以直接上数组版本没说就用哈希表确认输出找不到时返回0这点通常直接写在题目里但每次都要重点确认防止0和“无解”混淆。这三件事做好代码的骨架基本就定了剩下的就是往模板里填。7.2 一套可复用的滑动窗口模板我在讲解时经常强调滑动窗口不是靠背题而是靠一套可迁移的框架。这套框架除了能解“新词挖掘”还可以一字不改地解LeetCode 76 最小覆盖子串返回最短覆盖子串本身LeetCode 567 字符串的排列判断s2是否包含s1的排列LeetCode 438 找到字符串中所有字母异位词返回所有异位词起始索引。它们的共同点是在一个长串上维护一个可变窗口窗口内满足某种字符计数条件并求最短、判断存在性或统计满足条件的窗口。7.3 测试用例设计机试不像LeetCode有那么多隐藏测试但自己构造用例的能力仍然是拿分关键。我通常按这几个维度设计用例contentword期望输出用途基础覆盖ababaefeba3题目示例完全无覆盖abcdef0无解分支单字符aa1最小窗口word比content长aaa0长度边界word含重复字符aabbab2频次判断所有窗口都覆盖bbbbbb2收缩逻辑content包含word但分散acbaabc3不连续覆盖其中“word含重复字符”这个用例非常关键它专门用来验证window[ch]的频次计数是否严格正确。我见过有人把window[ch] need[ch]写成window[ch] need[ch]在这个用例下就会炸。7.4 三种语言的选型建议根据我的实际经验Python代码量最少适合快速AC推荐大多数考生使用。缺点是常数偏大但本题O(n)的复杂度下完全不是问题Java如果你主语言是Java直接用Java注意equals比较和Scanner读入的细节C追求极致性能或者主语言是C再选它。数组版代码里隐藏的越界风险比较多建议先用unordered_map版本AC再考虑优化。选语言的核心标准不是“哪个最强”而是“哪个你最熟”。机试现场时间紧张用不熟的语言写代码光是编译报错就能消耗大量时间。最后再分享一个个人体会滑动窗口这类题不要只看不写。我辅导过的人里十个有八个在实际手写时都会在valid的增减顺序上栽一次。这个坑踩过一次之后基本就形成肌肉记忆了以后再碰到字符串覆盖类的题闭着眼都能写对。所以建议你在本机上把这三种版各敲一遍跑一遍我上面列的测试用例体验会比读十篇文章都好。
华为OD机试“新词挖掘”题解：滑动窗口与最小覆盖子串的实战剖析
我最早看到“新词挖掘”这道题是在整理华为OD机试真题题库的时候。当时第一反应是——这不就是LeetCode 76题“最小覆盖子串”吗但仔细读完题以后发现出题人给这道经典滑动窗口题重新披了一层“自然语言处理”的外衣还顺势改了两个条件让不少直接背模板的考生在考场上摔了跟头。这篇文章就把这道题的题干、思路、以及Python/Java/C三种语言的实现讲透同时把我自己在调试过程中踩过的坑一并列出来给准备OD机试的朋友做个参考。如果你正在刷华为OD题库或者想通过一道题彻底搞懂滑动窗口这篇应该能帮到你。1. 真题还原新词挖掘到底在问什么1.1 题目描述与输入输出华为OD机试的“新词挖掘”题原题大意如下小华在负责公司的新词挖掘工作。给定一段文本content和一个候选新词word现在要在content中找到一个最短的连续子串使得该子串包含word中的所有字符并且每个字符的出现次数不少于word中对应字符的出现次数。如果找不到这样的子串返回0。注意这里有两个关键词“连续子串”和“包含”。连续子串很好理解就是content中一段连续的区域但“包含”并不是“作为子串出现”的意思而是字符覆盖——不要求word的字符在子串里连续排布。举个例子content ababaefword eba输出应该是3。仔细看content里有“eba”这个连续片段长度就是3它自然满足条件。再比如content aabbword ab最短子串是“ab”长度为2没问题。但如果改成content acbaword abc这里content里没有连续出现的“abc”但子串“acb”覆盖了a、b、c三个字符各一次长度为3所以答案是3。如果只会在content里找连续匹配“abc”的人这道题直接就漏解了。1.2 题目的考察点从面试和机试的视角看这道题不是一个孤立的知识点它至少同时考察了四样东西滑动窗口双指针的熟练度能否识别出“求满足条件的最短连续子串”这个经典结构哈希表/计数数组的使用怎么用O(1)的时间判断当前窗口是否覆盖了word对“覆盖”语义的准确理解窗口内的字符频次必须分别大于等于word里的字符频次边界条件的严谨性content比word短、word为空、存在大量重复字符等情况。这和LeetCode 76“最小覆盖子串”几乎一样唯一的差别是76题要求返回最小的那个子串这道题只要求返回长度。所以如果你刷过76题这道题基本就是送分题如果没刷过从零开始推滑动窗口考场上是比较紧张的。1.3 和标准“最小覆盖子串”的差异提醒我知道很多人刷题时会直接把76题的代码背下来这里提醒一个容易忽略的差异LeetCode 76的输入保证s和t都是英文字母而OD机试的输入是两行字符串没有明确说明字符集范围。这意味着用int[26]数组之前最好确认输入是否只包含小写字母如果出现大写字母、数字甚至中文int[26]就会越界。稳妥的做法是先用哈希表写一版AC之后想优化再退回数组。2. 暴力解法的死穴为什么O(n³)必挂2.1 最直观的暴力思路不熟悉滑动窗口的人看到这道题的第一反应一般是枚举。思路很直接枚举content的所有子串起点i从0到n-1终点j从i到n-1对每个子串统计字符频次与word的频次表比较如果覆盖记录当前子串长度取全局最小值。这个思路没有任何问题问题在于复杂度。假设content长度是nword长度是m枚举所有子串是O(n²)个统计每个子串的频次是O(n)与word频次表比较最坏也要O(字符集大小)或者O(m)。总复杂度大约是O(n³)这还只是乐观估计。2.2 把账算清楚华为OD机试里字符串长度常见范围是1到10^5。我们取几个数量级感受一下n 1000时n³ 10^9Python跑这个量级基本在超时边缘n 10^4时n³ 10^12无论什么语言都必挂n 10^5时n³ 10^15这已经不是算法问题是物理问题。实际上机试的时限通常只有1到2秒Python每秒大概能跑10^7到10^8次简单操作C大概能到10^9量级。10^12以上的操作量没有任何语言能在时限内跑完。有人会说我用前缀和优化掉统计频次的部分那也只能把O(n³)降到O(n² * 字符集大小)n 10^5时仍然是10^10量级照样超时。所以这条路从一开始就不该走。2.3 为什么“求最短”天然适合滑动窗口“最短连续子串”这个约束非常关键。它意味着最优解的左右边界之间一定是一段紧凑的区域而且这个区域随着右指针的移动只会整体向右推进不可能回退。这种“区间单调性”正是滑动窗口能成立的基础。如果题目改成“求所有覆盖word的子串数量”滑动窗口就需要配合其他技巧但恰好“求最短”这条约束让左右指针各走一遍就能得到答案时间复杂度掉到O(n)。3. 滑动窗口的核心逻辑左右指针如何配合3.1 窗口框架滑动窗口的代码框架我用伪代码描述一遍这个框架可以迁移到相当多的子串问题初始化左指针 left 0 初始化答案 ans 无穷大 初始化窗口计数字典 window 初始化 need word 的字符频次表 初始化 valid 0 // 已经满足频次要求的字符种类数 for right in 0..n-1: 把 content[right] 加入 window 如果这个字符在 need 中并且 window 中它的频次恰好等于 need 中的频次: valid 1 当 valid need 中不同字符的种类数: 尝试用当前窗口长度更新 ans 把 content[left] 移出 window left 1 如果移出的字符在 need 中并且移出后频次小于 need 中的频次: valid - 1关键点有两个右指针扩张每个字符最多被加入一次左指针收缩每个字符最多被移出一次valid计数它记录的是“已经满足条件的字符种类数”不是字符个数。3.2 为什么用“恰好等于”而不是“大于等于”来判断valid这是新手最容易写错的地方。假设need[a] 2window[a]从1变成2时应该valid加1如果window[a]继续变成3valid不能再加1因为a这个字符已经满足过一次条件了。所以代码里的判断条件一定是if window[ch] need[ch]: valid 1而不是if window[ch] need[ch]: valid 1后者会让某个字符反复累加valid导致valid超过need.size()后续while循环条件失效。3.3 收缩左指针时为什么不会错过最优解这是滑动窗口最难理解的一点。我的理解方式是当窗口覆盖word时先收缩左边界直到窗口不再覆盖收缩过程中记录窗口长度。这样每次覆盖状态下都尝试把左边多余的部分全部丢掉得到的是“以当前右指针为右端点的最短覆盖子串”。右指针继续向右移动后可能出现新的覆盖状态于是继续收缩。因为最优解一定存在某个右端点当右指针到达该右端点时左指针收缩到最大程度正好会计算到那个最优长度。所以不会漏。这个说法可能还是有点绕我习惯用一个比喻窗口就像一个橡皮筋右端不断向右拉拉到能包住目标时左端就使劲往右缩缩到再缩就包不住为止。每次拉和缩的过程中都记录一次最短的包住长度。因为橡皮筋左端永远不可能往左回退整个过程是单调的所以每个位置最多被左右指针各访问一次。这么说应该比较直觉了。3.4 边界情况预处理做题前先把边界堵上能省很多麻烦如果content长度小于word长度直接返回0如果word为空某些变体会出现返回0遍历结束时ans仍然为无穷大说明没有覆盖子串返回0。最后一步很重要因为“没有找到”和“找到了长度为0”在返回值上都是0但不处理ans还是无穷大直接返回会出错。4. Python实现清晰优先的标准解法4.1 完整代码Python是我推荐的机试首选项原因很简单库多、写起来快、不容易因为语法细节翻车。代码如下import sys from collections import defaultdict def min_window(content: str, word: str) - int: n, m len(content), len(word) if n m: return 0 need defaultdict(int) for ch in word: need[ch] 1 window defaultdict(int) left 0 valid 0 ans float(inf) for right in range(n): ch content[right] if ch in need: window[ch] 1 if window[ch] need[ch]: valid 1 while valid len(need): if right - left 1 ans: ans right - left 1 d content[left] left 1 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return 0 if ans float(inf) else ans def main(): lines sys.stdin.read().splitlines() if not lines: return content lines[0].strip() word lines[1].strip() if len(lines) 1 else print(min_window(content, word)) if __name__ __main__: main()这里我特意用了sys.stdin.read().splitlines()而不是input()因为机试的输入偶尔会带空行input()遇到空行会直接返回空字符串容易把content读错。用read()统一读取再分割稳一些。4.2 关键代码行逐句解读need defaultdict(int)这里用defaultdict而不是普通dict是为了避免每次判断if ch not in need: need[ch] 0这种样板代码。defaultdict在访问不存在的key时会自动初始化为0但注意if ch in need仍然需要显式判断因为这段逻辑关心“这个字符是否在need中出现过”而不是它的值。window[ch] 1和if window[ch] need[ch]只有从欠账变成刚好够的时候valid才加1。如果window[ch]已经超过need[ch]说明该字符之前就已经被计入valid了。while valid len(need)这个条件是“窗口已经覆盖了word”。len(need)是word中不同字符的种类数不是word长度。比如wordaabclen(need)3a、b、c而m4。收缩左边界时if window[d] need[d]: valid - 1这一行必须在window[d] - 1之前执行。如果先减频次再判断window[d]已经变小可能已经小于need[d]判断结果就错了。这个顺序问题我至少见过三个人栽过。4.3 时间复杂度与实测两个循环各自把left和right从0推到n中间常数操作O(1)总体O(n)。需要额外O(字符集大小)的空间来存频次。我本地用content长度为10^6、word长度为10^5的数据测过Python版本大约0.3到0.5秒跑完放在OD机试的1秒时限内完全够用。用defaultdict会比普通dict快一些因为它少了很多if key not in dict的判断。5. Java实现哈希表与自动装箱的坑5.1 完整代码Java的核心逻辑和Python完全一样但语言特性带来的坑不少。先看代码import java.util.*; public class Main { public static int minWindow(String content, String word) { int n content.length(); int m word.length(); if (n m) return 0; MapCharacter, Integer need new HashMap(); for (char c : word.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } MapCharacter, Integer window new HashMap(); int left 0, valid 0; int ans Integer.MAX_VALUE; for (int right 0; right n; right) { char c content.charAt(right); if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) 1); if (window.get(c).equals(need.get(c))) { valid; } } while (valid need.size()) { if (right - left 1 ans) { ans right - left 1; } char d content.charAt(left); left; if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return ans Integer.MAX_VALUE ? 0 : ans; } public static void main(String[] args) { Scanner sc new Scanner(System.in); String content sc.nextLine().trim(); String word sc.nextLine().trim(); System.out.println(minWindow(content, word)); } }5.2 equals而不是这是Java版最经典的坑。MapCharacter, Integer里的value是Integer对象当你写if (window.get(c) need.get(c)) {你以为在比较两个int值实际上比较的是两个Integer对象的引用。虽然JVM对-128到127之间的Integer有缓存两个值相同的Integer可能指向同一个对象但一旦某个字符出现次数超过127——这在长文本里非常常见——就可能返回falsevalid永远加不到need.size()整个逻辑直接崩掉。正确的写法是用.equals()if (window.get(c).equals(need.get(c))) {或者更稳妥地把value类型设计成int[]用数组索引字符直接从根上消灭自动装箱。5.3 Scanner读入的两行问题OD机试的Java模板经常用Scanner这里要注意sc.nextLine()读取一整行适合content和word都各占一行的情况如果题目输入是“content word”在同一行则应该用sc.next()而不是nextLine()否则会把整行读进去读完后最好.trim()一下防止首尾空格混入字符串导致字符频次统计错乱。我在实际测试中遇到过content末尾带\r的情况Windows换行符如果不trim\r会被当成一个普通字符加入window看起来不影响覆盖判断但在某些边界情况下会干扰窗口长度所以一律trim最稳。5.4 HashMap还是int[128]如果题目明确字符集只有小写字母可以用int[26]替代HashMap代码更简洁、性能更好。但如果题目不明确我建议第一版先上HashMap保证不越界。AC之后再优化成数组完全来得及。6. C实现从哈希表到定长数组的极致优化6.1 哈希表版本先保证正确C的unordered_map版本和Java思路一致但有几个C特有的点#include iostream #include string #include climits #include unordered_map using namespace std; int minWindow(const string content, const string word) { int n content.size(), m word.size(); if (n m) return 0; unordered_mapchar, int need, window; for (char c : word) need[c]; int left 0, valid 0; int ans INT_MAX; for (int right 0; right n; right) { char c content[right]; if (need.count(c)) { window[c]; if (window[c] need[c]) valid; } while (valid (int)need.size()) { if (right - left 1 ans) ans right - left 1; char d content[left]; left; if (need.count(d)) { if (window[d] need[d]) valid--; window[d]--; } } } return ans INT_MAX ? 0 : ans; } int main() { string content, word; getline(cin, content); getline(cin, word); cout minWindow(content, word) endl; return 0; }valid (int)need.size()这里的强转不是必须的但值得养成习惯。因为need.size()返回size_t无符号类型valid是int有符号类型两者比较时valid会被转换成无符号数一旦valid为负数逻辑错误时可能发生比较结果会变得非常诡异。强转后能让隐藏问题尽早暴露。6.2 定长数组版本榨干性能如果题目保证只含小写英文字母——这是华为OD题库里很常见的限制——那么数组版本会更合适#include iostream #include string #include climits using namespace std; int minWindow(const string content, const string word) { int n content.size(), m word.size(); if (n m) return 0; int need[26] {0}, window[26] {0}; int needTypes 0; for (char c : word) { int idx c - a; if (need[idx] 0) needTypes; need[idx]; } int left 0, valid 0; int ans INT_MAX; for (int right 0; right n; right) { int idx content[right] - a; if (need[idx] 0) { window[idx]; if (window[idx] need[idx]) valid; } while (valid needTypes) { if (right - left 1 ans) ans right - left 1; int leftIdx content[left] - a; left; if (need[leftIdx] 0) { if (window[leftIdx] need[leftIdx]) valid--; window[leftIdx]--; } } } return ans INT_MAX ? 0 : ans; } int main() { string content, word; getline(cin, content); getline(cin, word); cout minWindow(content, word) endl; return 0; }数组版的核心优化点消灭哈希开销unordered_map每次插入、查找都有哈希计算和可能的扩容而数组索引是O(1)直接寻址常数小很多needTypes代替need.size()因为数组没有size()用一个计数器记录word中不同字符的数量逻辑和哈希版完全一致越界风险content[right] - a这个表达式要求content[right]一定在a到z范围内否则下标越界轻则数组越界读到垃圾值重则程序崩溃。所以数组版只适用于明确字符集的场景。6.3 C版最常见的错误我见过不少人在C版里犯这些错误忘记初始化数组int need[26]如果不加{0}里面的值是随机的统计频次直接错乱。这大概是C新手最常踩的坑用strlen处理std::stringstrlen只对C风格字符串有效对std::string用.size()或.length()全局变量和局部变量重名比如全局有个left函数参数也叫left容易出现隐蔽错误。所以函数内尽量用清晰的局部变量名。7. 机试实战策略读题、编码与测试用例7.1 读题后的前30秒拿到这道题我建议前30秒只做三件事确认输入格式是两行还是一行空格分隔是否需要处理空行这决定了读入函数的选择确认字符集题目有没有说“只包含小写字母”如果说了后面可以直接上数组版本没说就用哈希表确认输出找不到时返回0这点通常直接写在题目里但每次都要重点确认防止0和“无解”混淆。这三件事做好代码的骨架基本就定了剩下的就是往模板里填。7.2 一套可复用的滑动窗口模板我在讲解时经常强调滑动窗口不是靠背题而是靠一套可迁移的框架。这套框架除了能解“新词挖掘”还可以一字不改地解LeetCode 76 最小覆盖子串返回最短覆盖子串本身LeetCode 567 字符串的排列判断s2是否包含s1的排列LeetCode 438 找到字符串中所有字母异位词返回所有异位词起始索引。它们的共同点是在一个长串上维护一个可变窗口窗口内满足某种字符计数条件并求最短、判断存在性或统计满足条件的窗口。7.3 测试用例设计机试不像LeetCode有那么多隐藏测试但自己构造用例的能力仍然是拿分关键。我通常按这几个维度设计用例contentword期望输出用途基础覆盖ababaefeba3题目示例完全无覆盖abcdef0无解分支单字符aa1最小窗口word比content长aaa0长度边界word含重复字符aabbab2频次判断所有窗口都覆盖bbbbbb2收缩逻辑content包含word但分散acbaabc3不连续覆盖其中“word含重复字符”这个用例非常关键它专门用来验证window[ch]的频次计数是否严格正确。我见过有人把window[ch] need[ch]写成window[ch] need[ch]在这个用例下就会炸。7.4 三种语言的选型建议根据我的实际经验Python代码量最少适合快速AC推荐大多数考生使用。缺点是常数偏大但本题O(n)的复杂度下完全不是问题Java如果你主语言是Java直接用Java注意equals比较和Scanner读入的细节C追求极致性能或者主语言是C再选它。数组版代码里隐藏的越界风险比较多建议先用unordered_map版本AC再考虑优化。选语言的核心标准不是“哪个最强”而是“哪个你最熟”。机试现场时间紧张用不熟的语言写代码光是编译报错就能消耗大量时间。最后再分享一个个人体会滑动窗口这类题不要只看不写。我辅导过的人里十个有八个在实际手写时都会在valid的增减顺序上栽一次。这个坑踩过一次之后基本就形成肌肉记忆了以后再碰到字符串覆盖类的题闭着眼都能写对。所以建议你在本机上把这三种版各敲一遍跑一遍我上面列的测试用例体验会比读十篇文章都好。
