华为OD机试的题库里有一类题目看起来人畜无害实际写起来却特别容易翻车比如这道“新词挖掘”。它名义上在考字符串处理实际上考的是滑动窗口和字符计数而且天然适合用Python、Java、C三种语言分别实现。很多准备华为OD机试的人一看到“新词挖掘”四个字就懵了觉得是什么NLP算法其实剥开包装就是一道标准的“找字母重排子串”问题。这篇文章我会把题目本质、三种语言的实现差异、完整推演过程和常见坑位一次讲透适合正在刷华为OD机试真题、准备面试手撕代码、或者想对比多语言实现思路的读者。1. 这道题到底在考什么从题目背景到核心考点1.1 华为OD机试的新词挖掘是道什么题先还原一下题目描述。给定一个单词 word 和一串文本 text定义一个“新词”为用 word 里面所有字母重新排列后能组成的任意字符串长度和 word 一样只是字母顺序变化。现在要求在 text 中找出所有“新词”出现的起始位置。举个例子。word abtext ababa。word 的字母重排后只有 ab 和 ba 两种新词。在 text 中逐个看过去下标0开始是 ab命中下标1开始是 ba命中下标2开始是 ab命中下标3开始是 ba命中。所以结果就是下标 [0, 1, 2, 3]或者说总共出现了 4 次。如果题目要求返回个数就返回 4如果要求返回起始位置就返回这个数组。这道题在华为OD机试里通常以“输出所有新词的起始下标”或“输出新词数量”的形式出现。熟悉力扣的朋友一眼就能看出来它其实就是 LeetCode 438 题 Find All Anagrams in a String 的双胞胎只是换了个“新词挖掘”的皮。机试之所以爱出这道题是因为它在不加任何复杂包装的情况下能同时考察三个基本功第一能不能看穿“新词”背后的本质是字符组合而不是什么高级算法第二能不能想到用固定长度的滑动窗口在 text 上平移第三能不能用高效的频率比较代替直观的排列枚举。这三个能力恰恰是机试高分的关键很多过了机试的人在面试手撕代码环节也被问过类似的题目。1.2 算法本质滑动窗口 字符计数初看这道题大部分人第一反应是枚举 word 的所有排列然后去 text 里找。这个思路在 word 很短的时候确实可行比如 word 长度是 2排列只有 2 种。但一旦 word 变长直接爆炸。word 长度为 10 时排列数是 10! 3628800 种光是生成排列就撑不住了更别提还要拿去匹配 text。所以这条路基本是死路。换个角度想两个字符串如果能通过重排互相得到说明它们的长度相同且每个字母出现的次数也完全相同。这才是“新词”的充要条件。基于这个结论我们根本不用枚举排列只需要检查 text 里每一个长度为 word 长度的子串统计子串中每个字母的出现次数和 word 中的字母次数对比。相等就是命中。那怎么高效地检查“每一个子串”呢这就是滑动窗口的用武之地。想象一个长度固定为 m 的窗口初始盖在 text 的前 m 个字符上。每次向右移动一格右边进一个字符左边出一个字符。窗口内的字母计数刚好只变化两个位置不需要重新统计整个窗口。这样每个字符最多被处理两次进一次、出一次整体时间复杂度只有 O(n)。用生活场景类比就像在流水线上检查固定大小的糖果盒你不需要每次把整盒糖果倒出来数一遍只需要知道上一盒是什么、新换进来的是什么、拿出去的是什么就能快速知道新这一盒的构成。复杂度方面设 text 长度为 nword 长度为 m时间统计 word 一次 O(m)滑动窗口遍历 text 一次 O(n)整体 O(n m)。空间两个固定大小的计数数组如果只考虑小写字母就是 int[26]可以认为是 O(1)。2. 多语言实现的核心细节Python/Java/C 三种解法对比2.1 Python题解用数组计数还是Counter先上完整的 Python 代码可以直接跑def find_new_words(text: str, word: str) - list: n, m len(text), len(word) if n m: return [] # 统计 word 中每个字母的出现次数 need [0] * 26 for ch in word: need[ord(ch) - ord(a)] 1 # 滑动窗口内的字母计数 window [0] * 26 res [] for i in range(n): # 右边进一个字符 window[ord(text[i]) - ord(a)] 1 # 左边出一个字符保证窗口长度恰好为 m if i m: window[ord(text[i - m]) - ord(a)] - 1 # 只有当窗口已经成形长度达到 m才比较 if i m - 1 and window need: res.append(i - m 1) return res if __name__ __main__: text ababa word ab print(find_new_words(text, word)) # [0, 1, 2, 3]Python 里很多人第一反应是用 collections.Counter代码也能写出来from collections import Counter def find_new_words_counter(text: str, word: str) - list: n, m len(text), len(word) if n m: return [] need Counter(word) window Counter(text[:m]) res [] if window need: res.append(0) for i in range(m, n): window[text[i]] 1 window[text[i - m]] - 1 if window[text[i - m]] 0: del window[text[i - m]] if window need: res.append(i - m 1) return res这段代码在逻辑上也能AC但在机试场景里我不建议用 Counter。原因有两点。第一Counter 本质是哈希表键值对操作和哈希计算的常数比数组大不少text 很长时差距会明显拉大。第二用 Counter 必须手动处理“计数减到 0 就删除键”的问题否则窗口里明明已经没有某个字母了Counter 里还留着键值为 0 的项比较结果就会出错。这个坑对新手非常不友好写漏了就是 WA而且报错还不直观。数组版就简单直接window need 直接用列表比较Python 会逐个元素比较写起来最省心。不过要注意数组版有个前提题目假设输入只包含小写字母。如果题目说“包含大小写字母”就得把数组扩到 128ASCII 可见字符范围或者用字典处理这时 Counter 的优势反而会体现出来。所以选型要看题目约束不是一味追求某一种写法。2.2 Java题解Arrays.equals 的正确打开方式Java 的代码结构和 Python 基本一致区别在于数组比较不能直接用 必须用 Arrays.equalsimport java.util.ArrayList; import java.util.Arrays; import java.util.List; public class NewWordSearch { public static ListInteger findNewWords(String text, String word) { ListInteger res new ArrayList(); int n text.length(), m word.length(); if (n m) { return res; } int[] need new int[26]; for (int i 0; i m; i) { need[word.charAt(i) - a]; } int[] window new int[26]; for (int i 0; i n; i) { window[text.charAt(i) - a]; if (i m) { window[text.charAt(i - m) - a]--; } if (i m - 1 Arrays.equals(window, need)) { res.add(i - m 1); } } return res; } public static void main(String[] args) { String text ababa; String word ab; System.out.println(findNewWords(text, word)); // [0, 1, 2, 3] } }Java 里最容易踩的坑有两个。第一个是charAt(i) - a的类型问题。charAt 返回的是 char但参与减法运算时会被自动提升为 int所以word.charAt(i) - a得到的是 0 到 25 的整数可以直接当数组下标用。这个机制很多从 C 转过来的人会不太习惯容易在 char 和 int 之间来回强转其实完全没必要。第二个是Arrays.equals和window need的区别。Java 里 比较的是引用地址两个数组内容一样但地址不同结果就是 false。所以必须用Arrays.equals。这个错误太典型了我自己见过不少人刷题时死在这一行上答案不对还找不到原因。2.3 C题解vector 直接比较的便捷C 里用 vector 存储计数因为 vector 重载了 可以直接比较两个 vector 的内容是否相等写起来是三门语言里最干净的一种#include iostream #include vector #include string using namespace std; vectorint findNewWords(const string text, const string word) { vectorint res; int n text.size(), m word.size(); if (n m) return res; vectorint need(26, 0), window(26, 0); for (char c : word) { need[c - a]; } for (int i 0; i n; i) { window[text[i] - a]; if (i m) { window[text[i - m] - a]--; } if (i m - 1 window need) { res.push_back(i - m 1); } } return res; } int main() { string text ababa; string word ab; vectorint res findNewWords(text, word); for (int pos : res) { cout pos ; } cout endl; // 0 1 2 3 return 0; }C 版本需要注意的地方有三个。第一如果题目字符串里可能包含大写字母c - a就会越界稳妥做法是直接开一个vectorint(128, 0)把字符强转成 int 当数组下标用牺牲一点空间换安全和通用。第二text[i]返回 char运算时自动提升为 int所以text[i] - a没有任何问题。第三C 的 vector 比较是逐元素比较和 Java 的 Arrays.equals、Python 的列表比较语义一致代码层面最不用动脑子。三套代码对比下来核心逻辑一模一样差异全在语法细节语言计数容器比较方式最容易踩的坑Pythonlist / Counter列表直接 Counter 需要手动删 0 值键Javaint[]Arrays.equals写成 比较的是引用Cvectorvector 直接 数组下标越界大小写混用3. 实操演练从读题到AC的完整流程3.1 机试中的输入输出怎么处理华为OD机试通常是在线编程核心是写核心逻辑函数输入输出格式会在题目里写明。常见输入格式是两行第一行是 text第二行是 word顺序千万别搞反我就见过有人把两行读反了样例输出一直对不上最后才发现是输入处理错了。Python 用 input() 读取记得加 strip() 去掉换行符text input().strip() word input().strip()Java 用 Scanner 或者 BufferedReader 都行Scanner sc new Scanner(System.in); String text sc.nextLine(); String word sc.nextLine();C 用 getline 或 cinstring text, word; getline(cin, text); getline(cin, word);输出的时候看清楚题目要求的是返回下标列表还是数量。如果是列表注意空格分隔还是换行分隔如果是数量直接输出整数。这些细节虽然不起眼但机试判题是按全量测试用例来的格式错了照样扣分。平时刷题时就养成“函数式编程”习惯把核心逻辑封装成函数输入输出单独处理。这样在线环境里只需要粘贴核心函数再根据题目要求补输入输出不容易乱。本地调试的话Python 用户装好解释器后在 VSCode 里配一下 Python 环境就行Java 用户配好 JDKC 用户准备好 g 或 MSVC。这些环境不复杂但提前配好能省出不少机试前的宝贵时间。3.2 手把手推演一个完整用例用一个稍微复杂的例子走一遍text cbabcacabword abc。word 长度 m 3text 长度 n 8。初始化 needa 出现 1 次b 出现 1 次c 出现 1 次。窗口模拟如下表i窗口起始位置窗口内容进出window计数是否命中0-cc-a:0,b:0,c:1窗口未满1-cbb-a:0,b:1,c:1窗口未满20cbaa-a:1,b:1,c:1命中位置031babbca:1,b:2,c:0未命中42abccba:1,b:1,c:1命中位置253bcaaaa:1,b:1,c:1命中位置364caccba:1,b:0,c:2未命中75acaaca:2,b:0,c:1未命中86cabbaa:1,b:1,c:1命中位置6最终结果是 [0, 2, 3, 6]。手动验证一下text[0..2] 是 cba是 abc 的重排text[2..4] 是 abc 本身text[3..5] 是 bcatext[6..8] 是 cab。全部命中。这个推演过程建议大家自己在纸上画一遍把“先进右、再出左”的顺序搞清楚。尤其注意 i3 的时候窗口内容已经变成了 [1,3] 的 bab而不是你以为的 [0,2] 的 cba。很多人写循环时把“出”写在“进”前面逻辑就全乱了。标准模板是先处理右边进来的字符再处理左边出去的字符最后比较顺序不能颠倒。3.3 三个提速和防坑的细节第一开头直接判断if n m: return 空结果。这个判断能省掉一大半边界情况不写虽然也能靠后面的逻辑兜住但每次循环都多一次无意义的判断代码也不干净。第二不要在主循环里重复计算ord(a)。Python 里可以把ord(a)存成变量 base减少函数调用Java 和 C 里 a 是常量没有这个问题。第三如果题目要求返回出现次数直接返回len(res)就行。如果要求输出所有起始位置就按位置输出。有些变体还会问“窗口中包含新词的最小滑动次数”那本质就变成贪心或者字符串匹配了别和本题搞混。4. 常见问题与避坑指南4.1 为什么用排序法直接超时我看到不少人一上来就写把 word 排序然后在 text 里截取等长子串也排序两个排序后的字符串相等就命中。代码很简洁sorted_word .join(sorted(word)) res [] for i in range(len(text) - len(word) 1): sub text[i:ilen(word)] if .join(sorted(sub)) sorted_word: res.append(i)这个思路在逻辑上完全正确问题出在复杂度上。每截取一个子串就要排序一次子串长度为 m单次排序 O(m log m)总共有 n-m1 个子串总复杂度 O((n-m) * m log m)。当 n 和 m 都到 10^5 级别时这种写法直接超时。滑动窗口解法为什么快因为它把“每次重新统计整个窗口”变成了“只更新窗口两端的字符”每次比较是 O(26)字母表大小而不是 O(m)。数据量越大差距越明显。4.2 边界条件总是出错的三个地方第一个是窗口成形前。窗口长度小于 m 时不应该比较很多人的代码在 i 从 0 开始时就进入比较逻辑导致把长度不足的子串也算进去。第二个是不等长情况。text 比 word 短直接返回空结果集不需要进入循环。第三个是重复字母。如果 word 本身有重复字母比如 aab那么 need 数组里 a 的计数是 2b 是 1。只要 window 对应位置能匹配上就行不需要额外去重。计数比较天然处理重复字母这也是计数法比排列法更适合这道题的原因之一。4.3 输入输出和工具链上的坑Python 的 input() 可能带回车换行处理前先 strip()养成习惯。Java 的 Scanner 遇到空行可能读取到空字符串如果 text 里有空串函数入口的判断能帮你兜住。C 的 getline 和 cin 混用时要小心缓冲区残留建议统一用 getline 读取所有行。VSCode 里跑 Python 记得选对解释器项目里如果同时装了多个 Python 环境容易跑到一个没装依赖的环境里。还有一个很实用的经验机试在线环境一般不支持本地调试所以写代码时要格外小心。建议先在本地把函数逻辑调通再套上去。尤其是数组下标这种问题本地跑一遍样例基本能发现别等到提交了才发现 WA。5. 从这道题延伸出去变体与实战场景5.1 常见变体题新词挖掘在机试和面试里经常换马甲出现常见的变体有几种返回所有新词本身而不是下标。做法是命中时用text[i-m1:i1]把子串加入结果集。大小写混合输入。把计数数组从 26 扩到 128或者用字典算法框架完全不用改。word 中有特殊字符或非字母字符。这时要用哈希表统计窗口和 word 的差用一个变量记录有多少个字符计数不匹配让比较从 O(26) 降到 O(1)。从“找定长子串”变成“找最短覆盖子串”。那是另一个经典问题滑动窗口变成长度可变需要维护左右两个指针和匹配计数。其中变体 3 的思路值得展开说一下因为这是面试加分项。核心是维护 need 和 window 两个数组外加一个变量 count表示当前窗口里有多少个字符已经和 need 完全匹配。每次进一个字符如果它进入后 window[c] need[c]count 加一每次出一个字符如果它离开前 window[c] need[c]count 减一。当 count 等于 need 中非零字符种类数时窗口就命中。这样比较的开销从 O(26) 变成 O(1)。普通机试题用不上这个优化但面试时主动讲出来会显得你确实理解了滑动窗口的本质。5.2 新词挖掘在真实场景里的应用新词挖掘本质上是“找字母重排子串”它在真实场景里应用不少。比如文本相似度检测中判断一段文字是否只是把关键词打乱了顺序比如搜索引擎里基于字符频率的关键词联想再比如一些游戏里的“成语接龙”或“字母重组”玩法底层都可以抽象成这个模型。理解了这一点你会发现刷题不只是为了华为OD机试它练的是你在给定约束下抽象问题、选择算法的能力。这种能力换到任何项目里都值钱。5.3 多语言实现的选择建议最后聊点个人经验。如果让我给准备机试的人一个建议不要贪多选一门语言刷透。Python 的优势是代码量最少、逻辑最直白适合把思路快速落地但要注意 Counter 的性能和坑。Java 的 Arrays.equals 是一个记忆点只要记住这个这类题基本不会写错。C 的 vector 比较最干净、性能最好但很多人对 STL 不太熟容易在 include 和编译上卡壳。我个人在实际刷题时用的是 Python因为机试场景下重点是 AC 速度和思路清晰度Python 的列表比较、切片和 input() 用起来太舒服了。但如果你准备面试手撕代码建议至少要能用 Java 或 C 写一遍同一道题。原因很简单面试官看你写 Python 时很可能会追问一句“如果输入规模再大十倍你这段代码哪里会变成瓶颈”你得能答得上来。你在三种语言之间对比过理解就会深入一层。这道“新词挖掘”题我从第一次见到现在前前后后在笔试、模拟面试、给人讲题时遇到过不下十次。每次讲它我都会强调一句话滑动窗口不是技巧而是一种思维习惯——在处理连续子数组、子串问题时先想一想能不能避免重复计算。这也是我判断一个人算法功底是否扎实的试金石。最后再分享一个小技巧刷这类滑动窗口题建议把“进一个、出一个、窗口满了才比较”这个模板写在备忘录里。遇到长度固定的子串匹配问题先套模板再根据题目要求改返回值。模板在手心里不慌机试那一刻你就赢了一半。