最近在刷华为机试编程模拟题10说实话这道题我断断续续卡了两天。模拟题10是整套模拟卷里最后一道题目描述很短看着就是个普通的字符串匹配但真做起来滑动窗口、哈希表、边界条件缺一不可稍不注意就超时或者漏结果。这题做完以后我把它从头到尾复盘了一遍包括题目拆解、暴力解法到滑动窗口解法的优化过程、代码实现、调试记录以及最后的备考建议。如果你也在准备华为od机试或者刚开始接触这类公司机试这篇文章可以当作一份现场记录来参考别当成标准答案看。1. 先搞清楚机试在考什么模拟题10的定位和考察逻辑1.1 华为机试的基本盘题型分布与评分机制在聊这道题之前先说我了解到的机试大环境。以常见的华为od机试为例新系统通常采用双机位线上考试考生需要准备两个摄像头一个对着正面一个对着侧面考试环境里不能有其他人手机也要按要求放到指定位置。流程上有很多细节要求这些网上都有我就不展开说了。对刷题有直接影响的是题目形态一般一套题会出2到3道编程题前两道偏基础后一道偏综合这套模拟题10对应的就是最后的综合题。评分机制也不是非黑即白。大部分场次按测试用例通过比例给分不是只有满分和零分两种结果。也就是说第一题拿满分、第二题拿满分第三题就算只过部分用例总分依然可能不低。这也是为什么很多备考攻略都在强调“第三题暴力混分也是策略”。但如果你想冲高分第三题肯定还是要认真对待的因为拉开差距的往往就是它。模拟题10这类题目考的就是这个位置的典型水平基础题你靠刷题量能堆出来综合题则需要你把多个知识点串起来现场设计出正确且不超时的解法。1.2 为什么“滑动窗口哈希表”适合当压轴题复盘的时候我一直在想一个问题为什么这种题适合当压轴因为它能同时考察三件事。第一你懂不懂用哈希表记录频次能不能正确处理重复元素第二你懂不懂双指针的移动逻辑窗口怎么滑才不会漏第三你有没有复杂度意识写出来的代码在大数据量下会不会超时。这三个能力恰好是机试里最常扣分的地方。很多同学不是不会写代码而是不会做复杂度预判。举个例子暴力遍历一遍看起来逻辑完全正确但数据量一上来就超时这种教训我至少在三道题里踩过。模拟题10恰好把这个问题暴露得特别彻底。所以我觉得值得单独写一篇来复盘把每一步思考过程都记录下来对你对我都有价值。2. 题目拆解和解题思路从暴力到滑窗2.1 先看题目串联子串定位先把题目贴出来。以下是我按考试输入输出格式整理后的版本和LeetCode 30类似但输入输出换成了机试常见的多组用例风格。题目描述给定一个字符串s和一个字符串数组wordswords中的所有字符串长度相同。找出s中所有恰好可以由words中所有字符串拼接形成的子串的起始位置words中的字符串可以按任意顺序排列。如果不存在不输出任何结果。要求下标按升序输出。输入格式barfoothenefoobar 2 foo bar输出格式0 9解释一下s barfoothenefoobarwords [foo, bar]从下标0开始可以拼出barfoo从下标9开始可以拼出foobar所以答案是0和9。注意下标从0开始多个结果用空格分隔。2.2 暴力解法为什么不行拿到题第一反应自然是枚举s中每个位置作为起点截取长度等于单词总长的子串然后把这个子串按单词长度切分再和words里的频次比对。逻辑非常直白我一分钟就能写完。但你算一下复杂度就明白了假设s长度n是10^4words数量m是5000单词长度len是5那么总窗口长度大概是25000已经超过s长度了实际用例可能不会这么极端但即便n10^4、m100、len5这种常规数据暴力也要做大概n乘m等于10^6次哈希操作加上每次截取字符串的拷贝常数非常大。在机试平台上这种写法基本会卡在一半用例上后面的测试点直接超时。所以暴力只能用来验证小样例不能作为最终方案付交。这也是机试备考里很关键的一个意识不要觉得能跑出正确结果就够了要主动去想最坏情况下的数据量。2.3 滑动窗口的优化思路以及一个容易被忽略的分组逻辑暴力慢在哪慢在每次换起点时都把窗口里的所有单词重新数一遍。但换个角度想words里每个单词长度都一样所以最终拼接出来的总长度是固定的。也就是说在s里匹配时窗口宽度是固定的。既然宽度固定就有优化空间窗口每次移动一个字符是浪费的因为只有移动一个单词长度后窗口里的单词切分方式才有意义。进一步想起点偏移量其实只有0到wordLen减1这几种情况。比如单词长度是3那么窗口的切分边界只能在索引0、3、6这个系列或者1、4、7这个系列或者2、5、8这个系列三组之间不会交叉。把每一组看成一条独立的滑轨每条滑轨上用双指针维护窗口内的单词频次就能做到每个字符最多进一次、出一次整体变成线性复杂度。这个分组的细节特别容易被忽略。我第二次写的时候直接对每个起点滑动没有按偏移量分组结果漏掉了很多情况。你想想如果不分组窗口每次移动一个字符单词的切分边界就全乱了根本没法保证每次截取的都是完整的单词。2.4 用matched计数加速匹配窗口滑动时如果每次都重新构造哈希表再和words的哈希表比较复杂度又会上去。比较的标准做法是维护一个matched变量表示当前窗口里已经匹配的单词种类数。右指针进入新单词时如果这个单词在words里需要的数量还没被窗口用尽就增加计数matched加一左指针移出单词时如果窗口里该单词数量刚好从满足变成了不满足matched就减一。当matched等于words中不同单词的总数时说明当前窗口正好包含words的全部单词此时左指针的位置就是一个答案。这个技巧能把每次窗口更新从遍历整个哈希表降到O(1)的平均时间。我在模拟题10里反复踩这个坑后面调试记录会细说。先把思路理清楚后面代码才能一遍过。3. 代码实现与边界细节3.1 C 实现代码这道题用C写有一个好处内存控制明确性能足够。我给出一版完整可跑的代码。#include bits/stdc.h using namespace std; vectorint findSubstring(string s, vectorstring words) { vectorint ans; if (s.empty() || words.empty()) return ans; int wordLen words[0].size(); int wordNum words.size(); int totalLen wordLen * wordNum; if ((int)s.size() totalLen) return ans; unordered_mapstring, int need; for (auto w : words) need[w]; for (int offset 0; offset wordLen; offset) { int left offset, right offset; unordered_mapstring, int window; int matched 0; while (right wordLen (int)s.size()) { string rWord s.substr(right, wordLen); right wordLen; if (need.count(rWord)) { window[rWord]; if (window[rWord] need[rWord]) matched; } while (right - left totalLen) { string lWord s.substr(left, wordLen); left wordLen; if (need.count(lWord)) { if (window[lWord] need[lWord]) matched--; window[lWord]--; } } if (matched (int)need.size()) { ans.push_back(left); } } } sort(ans.begin(), ans.end()); return ans; } int main() { string s; while (getline(cin, s)) { if (s.empty()) continue; int n; cin n; vectorstring words(n); for (int i 0; i n; i) cin words[i]; cin.ignore(); vectorint res findSubstring(s, words); if (res.empty()) { cout endl; } else { for (int i 0; i (int)res.size(); i) { if (i) cout ; cout res[i]; } cout endl; } } return 0; }几个关键点外层循环是offset取值范围是0到wordLen-1这是分组滑动的核心。matched比较的是need.size()不是wordNum。因为words里可能有重复单词需要统计的是不同字符串的种类数而不是单词总数。比如words [foo, foo]need.size()就是1窗口里只要有两个foo就满足matched最多为1。3.2 Python 实现代码如果机试允许用Python我的建议是能写Python就写Python开发效率高逻辑也更直观。但注意不要无脑使用Counter比较。def find_substring(s: str, words: list[str]) - list[int]: ans [] n len(s) if n 0 or not words: return ans word_len len(words[0]) word_num len(words) total_len word_len * word_num if n total_len: return ans need {} for w in words: need[w] need.get(w, 0) 1 for offset in range(word_len): left offset right offset window {} matched 0 while right word_len n: rword s[right:right word_len] right word_len if rword in need: window[rword] window.get(rword, 0) 1 if window[rword] need[rword]: matched 1 while right - left total_len: lword s[left:left word_len] left word_len if lword in need: if window[lword] need[lword]: matched - 1 window[lword] - 1 if matched len(need): ans.append(left) return sorted(ans)我在机试里通常用sys.stdin.read()读全部输入然后按行解析这样面对多组用例时不容易乱。Python的字符串切片和字典操作虽然方便但要注意不要让代码在循环里反复构造Counter对象否则数据量一大还是会超时。3.3 边界条件最容易翻车的四个地方第一个words为空或s为空直接返回空这个谁都知道但容易在输入处理阶段报错所以主函数里要加判断。第二个s长度小于所有单词拼接后的总长度直接返回空没必要再进循环这个判断能省不少时间。第三个重复单词的处理。这是最容易出错的地方。我的做法是matched等于need的大小need存的是不同字符串的目标次数。如果只统计单词总个数遇到重复单词就会多算或者漏算。第四个外层循环如果漏掉offset或者把offset写成0到n都会导致窗口切分边界错乱结果或漏或重。正确的做法是在0到wordLen-1之间枚举起点偏移然后每组内部保持固定步长wordLen滑动。3.4 输入输出的处理技巧机试和LeetCode最大的不同就是输入输出要自己处理。模拟题10这道题我给的输入格式是字符串一行、单词数量一行、每个单词一行。C里用getline读完第一行后再cin读数字和单词最后cin.ignore清掉换行符不然下一轮getline会读到空字符串。Python的话建议一次性sys.stdin.read()读完整段然后按空行或者固定格式解析。我在实际考试里见过不少同学因为输入解析出错明明算法写对了结果第一行就读不进去白白丢分。这种细节不练几次真的容易踩。4. 实测调试从超时到通过的完整记录4.1 第一版暴力解法写起来快但中等数据直接超时我一开始图省事写了暴力。本地小样例全过样例输出也对一上在线环境跑到第七个用例就卡住后面的测试点全部超时。这个现象我印象很深因为如果你的逻辑有错通常报WA报TLE说明逻辑大概率对但复杂度不合格。机试评分按通过用例比例给暴力能拿一部分分但拿不到满分。当时我意识到必须换思路。但怎么换很多人的误区是一上来就背滑动窗口模板其实应该先分析为什么暴力慢。暴力慢在重复计算。想清楚这一点再去想怎么复用之前的计算结果滑窗思路就顺理成章了。4.2 第二版滑动窗口方向对了但比较方式还是拖了后腿改成滑窗后我第一次写的比较逻辑是if window need: ans.append(left)Python里两个字典可以直接比较结果也对但窗口每次变动都要做一次全量比较。窗口长度可能是几十个单词比较一次就要遍历几十个键。窗口滑动n次整体复杂度又回到O(n乘m)还是超时。后来改成维护matched计数只在当前窗口满足条件时才记录结果。这个改动很小但性能差距巨大。实操中如果发现滑窗还是慢先检查是不是在循环里做了全量的字典比较。我见过不少人有这个习惯包括我自己第一反应总是“直接比较多方便”但机试不会给你留情面。4.3 第三版matched计数的减一逻辑顺序反了会出bugmatched减一的时机很容易写错。左指针移出单词时如果当前窗口里该单词的计数刚好等于need里的计数说明这个单词从“满足”变成了“不满足”matched要减一。注意要先判断再减window计数顺序反了window[lword]减1之后再判断结果就不对了。这个坑我调试了半个多小时最后是靠打印每一步的window和matched才发现的。你可以试一下这个场景words [a, b, a]need里a需要2次b需要1次窗口里已经有a两次、b一次此时matched等于2。如果左指针准备移出一个a判断window[a] need[a]成立matched先减成1然后window[a]减成1。如果顺序反了window[a]先减成1再比较window[a]和need[a]两者相等matched不减反而可能加错整个统计就乱了。4.4 常见问题速查表我把这一路踩过的坑整理成一个表格方便你对照检查。问题现象可能原因解决办法小数据全对大数据超时暴力枚举或循环内全量比较字典改成分组滑动窗口用matched计数结果少了一部分漏掉offse分组直接对每个起点滑动外层循环枚举0到wordLen-1结果重复matched比较的是单词总数不是种类数用len(need)判断而不是len(words)matched计数错乱先减window计数再判断匹配状态先判断window[word] need[word]再window[word]--输入读不到下一组没有处理换行符C用cin.ignorePython按行strip内存占用过高每轮循环重建哈希表只维护一个window字典在滑动时更新输出格式错误多打印了调试信息最终只输出结果一行多个数字用空格分隔表格里最后一条也提醒我们考试时别把调试打印留在最终代码里平时调试可以随意提交前一定要清理干净。我有一次就是忘记删for循环里的cout导致输出全是调试信息整题判0分这种失误太冤了。5. 从一道模拟题反推机试备考路线5.1 机试高频考点清单刷完模拟题10之后我顺了一遍机试常考的知识点发现其实是有规律可循的。准备机试不能只靠刷题量更要有一个清晰的考点地图。考点优先级典型题型字符串处理极高子串匹配、分割、替换、排序哈希表极高频次统计、去重、映射关系双指针高滑动窗口、快慢指针、收缩窗口排序高自定义排序、区间合并、Top K二分查找中高有序数组查找、最大值最小化贪心中高区间调度、跳跃游戏、分配问题DFS/BFS中高岛屿问题、迷宫、拓扑排序动态规划中背包、子序列、编辑距离前缀和中子数组和、区间查询并查集中低连通性、朋友圈、冗余连接模拟题10覆盖的是前三个考点所以它才能当压轴。你在备考时可以优先把字符串、哈希、双指针这三块练扎实再扩展排序和二分最后补图和动态规划。这个顺序能保证你在有限时间内拿到最多的分数。5.2 刷题策略模拟题怎么用才有价值很多人刷模拟题就是打开题目看一遍不会就去搜题解看完觉得“哦原来是这样”然后关掉下一题。这种刷法效果很差。我的做法是拿模拟题当考试题来对待限定时间比如整套卷子150分钟我就按150分钟做不管会不会先把能写的写出来统一提交再统一复盘。复盘的时候不要只记答案要记录三件事这个题为什么往这个方向想我的解法在哪个环节卡住了题解里有哪些细节是我没想到的。把这三件事写清楚这道题才真正变成你的。我刷模拟题10的时候就是因为把滑窗模板和匹配计数的细节彻底搞明白了后面再做类似题基本都能直接套用。5.3 考试时的实战技巧最后说几个考试时可以直接用的实战技巧。第一读题先看数据范围。看到n是10^4基本可以排除O(n平方)的解法看到n是10^5至少要想清楚能不能用O(n log n)看到字符串和单词长度固定优先考虑分组滑动窗口。数据范围是最便宜的提示很多题不需要你现场设计算法只需要你背过对应复杂度的模板。第二先暴力混分再优化。机试不是写给人看的代码是按通过用例比例拿分的。如果你只能写出暴力就先把暴力交上去拿一部分分然后在这个基础上优化。千万不要坐在那里干想最优解时间就这么耗没了。第三输出格式严格不能错。机试平台比对的是完整输出多一个空格、少一个换行都可能判错。建议交卷前把样例输出和你的输出逐字节对比。我一般是本地跑一遍样例再把重定向到文件里用diff命令对比这样最保险。第四时间分配。我的常见分配是第一题20分钟第二题30分钟第三题留40分钟以上。如果第一题15分钟还没头绪先跳到第二题。不要在一道题上死磕超过40分钟机试考的是总分不是单题满分。5.4 从模拟题10延伸的变形题学完滑窗以后我还专门找了一些变形题来巩固。这里说两个我看到就想起来的方向。第一个把“单词串联”改成“字符可重复的子串覆盖”。要求s中某个子串可以覆盖words里所有单词但可以多出其他字符这时候窗口就不是固定长度而是需要收缩的经典滑动窗口。思路类似但判断条件从“窗口长度刚好等于总长度”变成“窗口内部已经覆盖了所有单词”。第二个把“单词数组”改成“字符集合”要求返回最短覆盖子串。这是LeetCode 76的经典题本质也是滑窗加哈希表。在这个变体里窗口不再按固定步长移动而是left和right各自向前伸缩。理解了模拟题10里的matched计数再做这个变体会轻松很多。刷算法题就是这样一个模板吃透了能带走一片题目。模拟题10的价值不在于这道题本身而在于它把哈希表频次统计、固定窗口滑动、匹配计数、边界处理这几个知识点串在了一起值得反复咀嚼。最后说点实在的。我刷模拟题10最大的收获不是记住这道题的答案而是把“滑窗加哈希表”这套组合打法彻底练熟了。以前我遇到字符串匹配第一反应就是Counter硬算或者暴力截串现在会先看单词长度和窗口总长判断能不能用分组滑窗。这个转变本身就是刷模拟题的意义。你在考场上遇到的题大概率不是原题但背后的模型是重复出现的。如果这篇文章能帮你少走几个小时的弯路那就值了。后面我打算继续复盘这套模拟题的其他题目尤其是考频更高的贪心和动态规划到时候再跟大家细聊。 
长河君 · 2026/9/1 12:51:37 · 阅读 1.2k 华为OD机试模拟题10：滑动窗口与哈希表解字符串串联子串
最近在刷华为机试编程模拟题10说实话这道题我断断续续卡了两天。模拟题10是整套模拟卷里最后一道题目描述很短看着就是个普通的字符串匹配但真做起来滑动窗口、哈希表、边界条件缺一不可稍不注意就超时或者漏结果。这题做完以后我把它从头到尾复盘了一遍包括题目拆解、暴力解法到滑动窗口解法的优化过程、代码实现、调试记录以及最后的备考建议。如果你也在准备华为od机试或者刚开始接触这类公司机试这篇文章可以当作一份现场记录来参考别当成标准答案看。1. 先搞清楚机试在考什么模拟题10的定位和考察逻辑1.1 华为机试的基本盘题型分布与评分机制在聊这道题之前先说我了解到的机试大环境。以常见的华为od机试为例新系统通常采用双机位线上考试考生需要准备两个摄像头一个对着正面一个对着侧面考试环境里不能有其他人手机也要按要求放到指定位置。流程上有很多细节要求这些网上都有我就不展开说了。对刷题有直接影响的是题目形态一般一套题会出2到3道编程题前两道偏基础后一道偏综合这套模拟题10对应的就是最后的综合题。评分机制也不是非黑即白。大部分场次按测试用例通过比例给分不是只有满分和零分两种结果。也就是说第一题拿满分、第二题拿满分第三题就算只过部分用例总分依然可能不低。这也是为什么很多备考攻略都在强调“第三题暴力混分也是策略”。但如果你想冲高分第三题肯定还是要认真对待的因为拉开差距的往往就是它。模拟题10这类题目考的就是这个位置的典型水平基础题你靠刷题量能堆出来综合题则需要你把多个知识点串起来现场设计出正确且不超时的解法。1.2 为什么“滑动窗口哈希表”适合当压轴题复盘的时候我一直在想一个问题为什么这种题适合当压轴因为它能同时考察三件事。第一你懂不懂用哈希表记录频次能不能正确处理重复元素第二你懂不懂双指针的移动逻辑窗口怎么滑才不会漏第三你有没有复杂度意识写出来的代码在大数据量下会不会超时。这三个能力恰好是机试里最常扣分的地方。很多同学不是不会写代码而是不会做复杂度预判。举个例子暴力遍历一遍看起来逻辑完全正确但数据量一上来就超时这种教训我至少在三道题里踩过。模拟题10恰好把这个问题暴露得特别彻底。所以我觉得值得单独写一篇来复盘把每一步思考过程都记录下来对你对我都有价值。2. 题目拆解和解题思路从暴力到滑窗2.1 先看题目串联子串定位先把题目贴出来。以下是我按考试输入输出格式整理后的版本和LeetCode 30类似但输入输出换成了机试常见的多组用例风格。题目描述给定一个字符串s和一个字符串数组wordswords中的所有字符串长度相同。找出s中所有恰好可以由words中所有字符串拼接形成的子串的起始位置words中的字符串可以按任意顺序排列。如果不存在不输出任何结果。要求下标按升序输出。输入格式barfoothenefoobar 2 foo bar输出格式0 9解释一下s barfoothenefoobarwords [foo, bar]从下标0开始可以拼出barfoo从下标9开始可以拼出foobar所以答案是0和9。注意下标从0开始多个结果用空格分隔。2.2 暴力解法为什么不行拿到题第一反应自然是枚举s中每个位置作为起点截取长度等于单词总长的子串然后把这个子串按单词长度切分再和words里的频次比对。逻辑非常直白我一分钟就能写完。但你算一下复杂度就明白了假设s长度n是10^4words数量m是5000单词长度len是5那么总窗口长度大概是25000已经超过s长度了实际用例可能不会这么极端但即便n10^4、m100、len5这种常规数据暴力也要做大概n乘m等于10^6次哈希操作加上每次截取字符串的拷贝常数非常大。在机试平台上这种写法基本会卡在一半用例上后面的测试点直接超时。所以暴力只能用来验证小样例不能作为最终方案付交。这也是机试备考里很关键的一个意识不要觉得能跑出正确结果就够了要主动去想最坏情况下的数据量。2.3 滑动窗口的优化思路以及一个容易被忽略的分组逻辑暴力慢在哪慢在每次换起点时都把窗口里的所有单词重新数一遍。但换个角度想words里每个单词长度都一样所以最终拼接出来的总长度是固定的。也就是说在s里匹配时窗口宽度是固定的。既然宽度固定就有优化空间窗口每次移动一个字符是浪费的因为只有移动一个单词长度后窗口里的单词切分方式才有意义。进一步想起点偏移量其实只有0到wordLen减1这几种情况。比如单词长度是3那么窗口的切分边界只能在索引0、3、6这个系列或者1、4、7这个系列或者2、5、8这个系列三组之间不会交叉。把每一组看成一条独立的滑轨每条滑轨上用双指针维护窗口内的单词频次就能做到每个字符最多进一次、出一次整体变成线性复杂度。这个分组的细节特别容易被忽略。我第二次写的时候直接对每个起点滑动没有按偏移量分组结果漏掉了很多情况。你想想如果不分组窗口每次移动一个字符单词的切分边界就全乱了根本没法保证每次截取的都是完整的单词。2.4 用matched计数加速匹配窗口滑动时如果每次都重新构造哈希表再和words的哈希表比较复杂度又会上去。比较的标准做法是维护一个matched变量表示当前窗口里已经匹配的单词种类数。右指针进入新单词时如果这个单词在words里需要的数量还没被窗口用尽就增加计数matched加一左指针移出单词时如果窗口里该单词数量刚好从满足变成了不满足matched就减一。当matched等于words中不同单词的总数时说明当前窗口正好包含words的全部单词此时左指针的位置就是一个答案。这个技巧能把每次窗口更新从遍历整个哈希表降到O(1)的平均时间。我在模拟题10里反复踩这个坑后面调试记录会细说。先把思路理清楚后面代码才能一遍过。3. 代码实现与边界细节3.1 C 实现代码这道题用C写有一个好处内存控制明确性能足够。我给出一版完整可跑的代码。#include bits/stdc.h using namespace std; vectorint findSubstring(string s, vectorstring words) { vectorint ans; if (s.empty() || words.empty()) return ans; int wordLen words[0].size(); int wordNum words.size(); int totalLen wordLen * wordNum; if ((int)s.size() totalLen) return ans; unordered_mapstring, int need; for (auto w : words) need[w]; for (int offset 0; offset wordLen; offset) { int left offset, right offset; unordered_mapstring, int window; int matched 0; while (right wordLen (int)s.size()) { string rWord s.substr(right, wordLen); right wordLen; if (need.count(rWord)) { window[rWord]; if (window[rWord] need[rWord]) matched; } while (right - left totalLen) { string lWord s.substr(left, wordLen); left wordLen; if (need.count(lWord)) { if (window[lWord] need[lWord]) matched--; window[lWord]--; } } if (matched (int)need.size()) { ans.push_back(left); } } } sort(ans.begin(), ans.end()); return ans; } int main() { string s; while (getline(cin, s)) { if (s.empty()) continue; int n; cin n; vectorstring words(n); for (int i 0; i n; i) cin words[i]; cin.ignore(); vectorint res findSubstring(s, words); if (res.empty()) { cout endl; } else { for (int i 0; i (int)res.size(); i) { if (i) cout ; cout res[i]; } cout endl; } } return 0; }几个关键点外层循环是offset取值范围是0到wordLen-1这是分组滑动的核心。matched比较的是need.size()不是wordNum。因为words里可能有重复单词需要统计的是不同字符串的种类数而不是单词总数。比如words [foo, foo]need.size()就是1窗口里只要有两个foo就满足matched最多为1。3.2 Python 实现代码如果机试允许用Python我的建议是能写Python就写Python开发效率高逻辑也更直观。但注意不要无脑使用Counter比较。def find_substring(s: str, words: list[str]) - list[int]: ans [] n len(s) if n 0 or not words: return ans word_len len(words[0]) word_num len(words) total_len word_len * word_num if n total_len: return ans need {} for w in words: need[w] need.get(w, 0) 1 for offset in range(word_len): left offset right offset window {} matched 0 while right word_len n: rword s[right:right word_len] right word_len if rword in need: window[rword] window.get(rword, 0) 1 if window[rword] need[rword]: matched 1 while right - left total_len: lword s[left:left word_len] left word_len if lword in need: if window[lword] need[lword]: matched - 1 window[lword] - 1 if matched len(need): ans.append(left) return sorted(ans)我在机试里通常用sys.stdin.read()读全部输入然后按行解析这样面对多组用例时不容易乱。Python的字符串切片和字典操作虽然方便但要注意不要让代码在循环里反复构造Counter对象否则数据量一大还是会超时。3.3 边界条件最容易翻车的四个地方第一个words为空或s为空直接返回空这个谁都知道但容易在输入处理阶段报错所以主函数里要加判断。第二个s长度小于所有单词拼接后的总长度直接返回空没必要再进循环这个判断能省不少时间。第三个重复单词的处理。这是最容易出错的地方。我的做法是matched等于need的大小need存的是不同字符串的目标次数。如果只统计单词总个数遇到重复单词就会多算或者漏算。第四个外层循环如果漏掉offset或者把offset写成0到n都会导致窗口切分边界错乱结果或漏或重。正确的做法是在0到wordLen-1之间枚举起点偏移然后每组内部保持固定步长wordLen滑动。3.4 输入输出的处理技巧机试和LeetCode最大的不同就是输入输出要自己处理。模拟题10这道题我给的输入格式是字符串一行、单词数量一行、每个单词一行。C里用getline读完第一行后再cin读数字和单词最后cin.ignore清掉换行符不然下一轮getline会读到空字符串。Python的话建议一次性sys.stdin.read()读完整段然后按空行或者固定格式解析。我在实际考试里见过不少同学因为输入解析出错明明算法写对了结果第一行就读不进去白白丢分。这种细节不练几次真的容易踩。4. 实测调试从超时到通过的完整记录4.1 第一版暴力解法写起来快但中等数据直接超时我一开始图省事写了暴力。本地小样例全过样例输出也对一上在线环境跑到第七个用例就卡住后面的测试点全部超时。这个现象我印象很深因为如果你的逻辑有错通常报WA报TLE说明逻辑大概率对但复杂度不合格。机试评分按通过用例比例给暴力能拿一部分分但拿不到满分。当时我意识到必须换思路。但怎么换很多人的误区是一上来就背滑动窗口模板其实应该先分析为什么暴力慢。暴力慢在重复计算。想清楚这一点再去想怎么复用之前的计算结果滑窗思路就顺理成章了。4.2 第二版滑动窗口方向对了但比较方式还是拖了后腿改成滑窗后我第一次写的比较逻辑是if window need: ans.append(left)Python里两个字典可以直接比较结果也对但窗口每次变动都要做一次全量比较。窗口长度可能是几十个单词比较一次就要遍历几十个键。窗口滑动n次整体复杂度又回到O(n乘m)还是超时。后来改成维护matched计数只在当前窗口满足条件时才记录结果。这个改动很小但性能差距巨大。实操中如果发现滑窗还是慢先检查是不是在循环里做了全量的字典比较。我见过不少人有这个习惯包括我自己第一反应总是“直接比较多方便”但机试不会给你留情面。4.3 第三版matched计数的减一逻辑顺序反了会出bugmatched减一的时机很容易写错。左指针移出单词时如果当前窗口里该单词的计数刚好等于need里的计数说明这个单词从“满足”变成了“不满足”matched要减一。注意要先判断再减window计数顺序反了window[lword]减1之后再判断结果就不对了。这个坑我调试了半个多小时最后是靠打印每一步的window和matched才发现的。你可以试一下这个场景words [a, b, a]need里a需要2次b需要1次窗口里已经有a两次、b一次此时matched等于2。如果左指针准备移出一个a判断window[a] need[a]成立matched先减成1然后window[a]减成1。如果顺序反了window[a]先减成1再比较window[a]和need[a]两者相等matched不减反而可能加错整个统计就乱了。4.4 常见问题速查表我把这一路踩过的坑整理成一个表格方便你对照检查。问题现象可能原因解决办法小数据全对大数据超时暴力枚举或循环内全量比较字典改成分组滑动窗口用matched计数结果少了一部分漏掉offse分组直接对每个起点滑动外层循环枚举0到wordLen-1结果重复matched比较的是单词总数不是种类数用len(need)判断而不是len(words)matched计数错乱先减window计数再判断匹配状态先判断window[word] need[word]再window[word]--输入读不到下一组没有处理换行符C用cin.ignorePython按行strip内存占用过高每轮循环重建哈希表只维护一个window字典在滑动时更新输出格式错误多打印了调试信息最终只输出结果一行多个数字用空格分隔表格里最后一条也提醒我们考试时别把调试打印留在最终代码里平时调试可以随意提交前一定要清理干净。我有一次就是忘记删for循环里的cout导致输出全是调试信息整题判0分这种失误太冤了。5. 从一道模拟题反推机试备考路线5.1 机试高频考点清单刷完模拟题10之后我顺了一遍机试常考的知识点发现其实是有规律可循的。准备机试不能只靠刷题量更要有一个清晰的考点地图。考点优先级典型题型字符串处理极高子串匹配、分割、替换、排序哈希表极高频次统计、去重、映射关系双指针高滑动窗口、快慢指针、收缩窗口排序高自定义排序、区间合并、Top K二分查找中高有序数组查找、最大值最小化贪心中高区间调度、跳跃游戏、分配问题DFS/BFS中高岛屿问题、迷宫、拓扑排序动态规划中背包、子序列、编辑距离前缀和中子数组和、区间查询并查集中低连通性、朋友圈、冗余连接模拟题10覆盖的是前三个考点所以它才能当压轴。你在备考时可以优先把字符串、哈希、双指针这三块练扎实再扩展排序和二分最后补图和动态规划。这个顺序能保证你在有限时间内拿到最多的分数。5.2 刷题策略模拟题怎么用才有价值很多人刷模拟题就是打开题目看一遍不会就去搜题解看完觉得“哦原来是这样”然后关掉下一题。这种刷法效果很差。我的做法是拿模拟题当考试题来对待限定时间比如整套卷子150分钟我就按150分钟做不管会不会先把能写的写出来统一提交再统一复盘。复盘的时候不要只记答案要记录三件事这个题为什么往这个方向想我的解法在哪个环节卡住了题解里有哪些细节是我没想到的。把这三件事写清楚这道题才真正变成你的。我刷模拟题10的时候就是因为把滑窗模板和匹配计数的细节彻底搞明白了后面再做类似题基本都能直接套用。5.3 考试时的实战技巧最后说几个考试时可以直接用的实战技巧。第一读题先看数据范围。看到n是10^4基本可以排除O(n平方)的解法看到n是10^5至少要想清楚能不能用O(n log n)看到字符串和单词长度固定优先考虑分组滑动窗口。数据范围是最便宜的提示很多题不需要你现场设计算法只需要你背过对应复杂度的模板。第二先暴力混分再优化。机试不是写给人看的代码是按通过用例比例拿分的。如果你只能写出暴力就先把暴力交上去拿一部分分然后在这个基础上优化。千万不要坐在那里干想最优解时间就这么耗没了。第三输出格式严格不能错。机试平台比对的是完整输出多一个空格、少一个换行都可能判错。建议交卷前把样例输出和你的输出逐字节对比。我一般是本地跑一遍样例再把重定向到文件里用diff命令对比这样最保险。第四时间分配。我的常见分配是第一题20分钟第二题30分钟第三题留40分钟以上。如果第一题15分钟还没头绪先跳到第二题。不要在一道题上死磕超过40分钟机试考的是总分不是单题满分。5.4 从模拟题10延伸的变形题学完滑窗以后我还专门找了一些变形题来巩固。这里说两个我看到就想起来的方向。第一个把“单词串联”改成“字符可重复的子串覆盖”。要求s中某个子串可以覆盖words里所有单词但可以多出其他字符这时候窗口就不是固定长度而是需要收缩的经典滑动窗口。思路类似但判断条件从“窗口长度刚好等于总长度”变成“窗口内部已经覆盖了所有单词”。第二个把“单词数组”改成“字符集合”要求返回最短覆盖子串。这是LeetCode 76的经典题本质也是滑窗加哈希表。在这个变体里窗口不再按固定步长移动而是left和right各自向前伸缩。理解了模拟题10里的matched计数再做这个变体会轻松很多。刷算法题就是这样一个模板吃透了能带走一片题目。模拟题10的价值不在于这道题本身而在于它把哈希表频次统计、固定窗口滑动、匹配计数、边界处理这几个知识点串在了一起值得反复咀嚼。最后说点实在的。我刷模拟题10最大的收获不是记住这道题的答案而是把“滑窗加哈希表”这套组合打法彻底练熟了。以前我遇到字符串匹配第一反应就是Counter硬算或者暴力截串现在会先看单词长度和窗口总长判断能不能用分组滑窗。这个转变本身就是刷模拟题的意义。你在考场上遇到的题大概率不是原题但背后的模型是重复出现的。如果这篇文章能帮你少走几个小时的弯路那就值了。后面我打算继续复盘这套模拟题的其他题目尤其是考频更高的贪心和动态规划到时候再跟大家细聊。