LeetCode 30 串联所有单词的子串

题目回顾给定字符串s和字符串数组words所有单词长度相同找出s中恰好串联所有words单词一次的子串起始下标。 要求子串长度 words.length × 单词长度子串必须恰好包含全部单词无多余、无缺失顺序不限单词全部等长是本题核心突破口一、先提取关键变量定义javaint m words.length; // 单词总个数 int n words[0].length; // 单个单词固定长度 int ls s.length(); // 字符串s总长度 ListInteger res new ArrayList(); // 存储所有合法起始下标总窗口固定长度windowLen m * n二、整体算法核心思想滑动窗口 哈希差集differ核心优化点单词长度均为n所有合法起点只能是0,1,...,n-1举例单词长度 3合法起始偏移只有 0、1、2偏移 3 等价于偏移 0 的下一轮窗口无需重复遍历。 外层循环for (int i 0; i n; i)枚举所有起始偏移。用differ哈希表维护「窗口内单词」和「目标 words 单词」的差值key单词value窗口内计数 - 目标计数differ为空 窗口单词和目标完全匹配找到合法起点滑动窗口步长固定为n一次滑动一个单词距离不用逐个字符滑动大幅降低时间复杂度。三、逐段拆解代码逻辑外层循环枚举所有起始偏移 i ∈ [0, n-1]javafor (int i 0; i n; i) { // 剩余字符不足以放下一个完整窗口直接退出循环 if (i m * n ls) break; // 差值哈希表记录窗口与words的计数差 MapString, Integer differ new HashMap(); // 1. 初始化第一个窗口 [i, im*n) for (int j 0; j m; j) { String word s.substring(i j * n, i (j 1) * n); differ.put(word, differ.getOrDefault(word, 0) 1); } // 2. 减去目标单词的计数得到差值 for (String word : words) { differ.put(word, differ.getOrDefault(word, 0) - 1); if (differ.get(word) 0) differ.remove(word); } // 3. 滑动窗口步长n for (int start i; start ls - m * n 1; start n) { // 不是第一个窗口需要移除滑出的单词、加入新滑入的单词 if (start ! i) { // 新增进窗口的单词窗口末尾新单词 String newWord s.substring(start (m - 1) * n, start m * n); differ.put(newWord, differ.getOrDefault(newWord, 0) 1); if (differ.get(newWord) 0) differ.remove(newWord); // 滑出窗口的单词窗口最左侧旧单词 String outWord s.substring(start - n, start); differ.put(outWord, differ.getOrDefault(outWord, 0) - 1); if (differ.get(outWord) 0) differ.remove(outWord); } // 差值表为空窗口完全匹配记录起始下标 if (differ.isEmpty()) res.add(start); } }步骤 1初始化首个窗口javafor (int j 0; j m; j) { String word s.substring(i j * n, i (j 1) * n); differ.put(word, differ.getOrDefault(word, 0) 1); }从偏移i开始截取连续m个单词长度片段存入differ计数 1。 此时differ存储当前窗口单词出现次数。步骤 2减去目标 words 的计数构建差值表javafor (String word : words) { differ.put(word, differ.getOrDefault(word, 0) - 1); if (differ.get(word) 0) differ.remove(word); }逻辑窗口单词计数 - 目标单词计数 差值差值为 0 直接删除 key保证differ.isEmpty()可以作为匹配判断条件 举例 窗口[foo,bar]目标 words[bar,foo]差值全部抵消differ 为空匹配成功。步骤 3滑动窗口循环核心滑动逻辑start是当前窗口的起始下标每次向右滑动n个字符一个单词长度javaif (start ! i) { // 1. 窗口右滑一格尾部新增一个单词 String newWord s.substring(start (m - 1) * n, start m * n); differ.put(newWord, differ.getOrDefault(newWord, 0) 1); if (differ.get(newWord) 0) differ.remove(newWord); // 2. 窗口左侧滑出一个旧单词 String outWord s.substring(start - n, start); differ.put(outWord, differ.getOrDefault(outWord, 0) - 1); if (differ.get(outWord) 0) differ.remove(outWord); }滑动窗口变化可视化 旧窗口[start-n, start-nm*n)新窗口[start, startm*n)滑出最左侧[start-n, start)单词新增最右侧[start(m-1)*n, startm*n)单词匹配判断javaif (differ.isEmpty()) res.add(start);differ中无任何差值说明窗口内单词种类、数量完全和 words 一致记录起始下标。四、核心设计亮点为什么效率高只枚举 0~n-1 偏移单词定长 n任何合法起点模 n 必然落在 0~n-1其余偏移会重复计算直接砍掉大量无效遍历。差值哈希表 differ不需要维护两张 HashMap窗口表、目标表只用一张表存储差值空间减半判匹配仅需判断是否为空。窗口滑动步长为 n不逐字符滑动一次滑动一个完整单词时间复杂度大幅优化。差值为 0 立刻删除 key简化判空逻辑。五、完整执行示例演示输入s barfoothefoobarman, words [foo,bar]m2, n3, windowLen6外层循环 i0、1、2 以 i0 举例初始化首窗口 start0截取barfoodiffer 计数bar:1, foo:1减去目标 words 计数差值全部归零differ 为空存入结果 0窗口滑动到 start3滑出 bar新增 the → differ 出现差值不匹配窗口滑动到 start9滑出 the新增 bar → differ 再次为空存入结果 9最终输出[0,9]与题目样例一致。六、易错点拆解边界判断i m * n ls break偏移 i 剩余字符不足以放下完整窗口后续全部无效直接跳出外层循环。substring 左闭右开s.substring(a,b)截取[a,b)截取单词时区间计算必须精准。滑动时先加新单词、再减旧单词 顺序不能颠倒否则差值计算错误。差值等于 0 必须移除 key 如果保留 key 值 0differ.isEmpty()永远为 false无法识别匹配窗口。窗口循环上限start ls - m * n 1保证窗口右边界不越界start m*n ≤ ls。七、复杂度分析设字符串长度S单词总数m单词长度n外层循环最多执行n次单次外层内滑动窗口最多遍历S/n次 总时间复杂度O(n × S/n) O(S)线性复杂度最优解法。 空间复杂度O(m)哈希表最多存储 m 个单词。八、代码优缺点总结优点线性时间复杂度暴力枚举每个起点的 O (S×m) 解法大幅优化只用一张差值哈希表空间开销小滑动窗口步长为单词长度无无效字符遍历。