尧图网页设计 
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是 AlgoNote「算法通关手册」中 LeetCode 0030. 串联所有单词的子串与哈希表基础文档展开原理讲解。读完本文你将掌握如何把「单词全排列匹配」问题等价转化为「定长窗口内词频统计」问题以及用哈希表实现 $O(1)$ 词频比较的关键技巧。1. 题目概述1.1 题目大意给定一个字符串s和一个字符串数组words其中words中所有字符串长度相同。s中的「串联子串」是指一个包含words中所有字符串、以任意顺序排列连接起来的子串。例如若words [ab,cd,ef]那么abcdef、abefcd、cdabef、cdefab、efabcd、efcdab都是串联子串而acdbef不是因为它不是任何words排列的连接。要求返回所有串联子串在s中的开始索引答案顺序不限。1.2 数据范围题目约束$1 \le s.length \le 10^4$$1 \le words.length \le 5000$$1 \le words[i].length \le 30$words[i]与s仅由小写英文字母组成。1.3 示例分析示例 1输入s barfoothefoobarman, words [foo,bar] 输出[0,9] 解释words.length 2 且 words[i].length 3因此串联子串长度必须为 6。 - 子串 barfoo 起始于位置 0是 [bar,foo] 顺序排列的连接 - 子串 foobar 起始于位置 9是 [foo,bar] 顺序排列的连接。 输出顺序无关紧要返回 [9,0] 同样正确。示例 2输入s wordgoodgoodgoodbestword, words [word,good,best,word] 输出[] 解释words.length 4 且 words[i].length 4串联子串长度必须为 16。 s 中不存在长度为 16 且等于 words 任意排列连接的子串返回空数组。2. 核心思想固定长度滑动窗口 哈希表词频比较2.1 关键观察全排列匹配等价于词频匹配直接枚举words的所有排列再在s中查找是不可行的——words.length最大可达 5000全排列数量是阶乘级爆炸。这里需要抓住问题的两个结构特性窗口长度固定所有单词等长因此任一串联子串的长度必然等于 $word_length \times word_count$每个单词长度 × 单词个数。这个长度是常量与排列顺序无关。匹配等价于词频相等串联子串是words中所有单词各取一次、以任意顺序拼接的结果。只要一个窗口按单词长度切分后每种单词的出现次数恰好等于words中该单词的出现次数它就是一个串联子串——顺序完全由词频决定无需关心排列。于是「找全排列」这一 NP 式的枚举问题被降维成了「固定长度窗口内的词频对比」问题这正是本仓库固定长度滑动窗口章节所描述的标准应用场景窗口大小固定用于统计或查找长度为 $k$ 的区间性质。2.2 哈希表的作用$O(1)$ 词频比较词频对比使用哈希表完成以单词为键key、出现次数为值value。哈希表通过哈希函数 $Hash(key)$ 将键映射到存储位置实现高效插入与查找原理详见哈希表基础文档。Python 中直接用dict即可两个字典的相等比较current_count target_count会逐一比对键与值且仅在键集合完全一致时才相等天然满足「词频完全匹配」的语义。3. 算法步骤详解步骤 1计算窗口大小串联子串总长度$$total_length word_length \times word_count$$其中word_length len(words[0])题目保证所有单词等长word_count len(words)。步骤 2构建目标词频哈希表target_count遍历words统计每个单词出现次数。注意words中可能存在重复单词如示例 2 中的word出现两次因此必须用计数而非集合去重。步骤 3滑动窗口逐一切片检查从s的每个可能起始位置start范围0到len(s) - total_length出发截取长度为total_length的窗口子串按word_length为步长将窗口切成word_count个单词用哈希表统计这些单词的出现次数current_count。步骤 4匹配判断若current_count target_count则当前窗口是串联子串将start加入结果数组。边界处理若s、words或words[0]为空直接返回空列表若len(s) total_length窗口根本无法放下直接返回空列表。4. 完整代码实现思路 1滑动窗口 哈希表class Solution: def findSubstring(self, s: str, words: List[str]) - List[int]: 找到所有串联子串的起始位置 if not s or not words or not words[0]: return [] # 获取基本参数 word_length len(words[0]) # 每个单词的长度 word_count len(words) # 单词数量 total_length word_length * word_count # 串联子串的总长度 # 如果字符串长度小于串联子串长度直接返回空列表 if len(s) total_length: return [] # 构建目标单词计数哈希表 target_count {} for word in words: target_count[word] target_count.get(word, 0) 1 result [] # 遍历所有可能的起始位置 for start in range(len(s) - total_length 1): # 获取当前窗口的子串 window s[start:start total_length] # 将窗口按单词长度分割 window_words [] for i in range(0, total_length, word_length): word window[i:i word_length] window_words.append(word) # 统计当前窗口的单词出现次数 current_count {} for word in window_words: current_count[word] current_count.get(word, 0) 1 # 检查是否匹配目标计数 if current_count target_count: result.append(start) return result代码要点说明dict.get(word, 0) 1是 Python 中简洁的计数惯用法等价于「存在则累加、不存在则置 1」与collections.Counter效果一致但零依赖range(0, total_length, word_length)以单词长度为步长完成窗口切片切出的单词数恰好等于word_count两个dict直接比较会同时校验键集合与每个键对应的值这里恰好实现了「词频完全一致」的判定无需手写逐键循环。5. 复杂度分析维度复杂度说明时间复杂度$O(n \times m \times k)$其中 $n$ 为s的长度$m$ 为words的长度$k$ 为每个单词的长度。需要检查 $O(n)$ 个起始位置每个位置需切分并统计 $O(m)$ 个单词每个单词的切片与比较开销为 $O(k)$空间复杂度$O(m \times k)$存储目标词频哈希表与当前窗口词频哈希表各含至多 $m$ 个键、每键长度为 $k$在本题数据范围$n \le 10^4$、$m \le 5000$、$k \le 30$下该朴素滑动窗口版本逻辑清晰、易于验证可作为面试中的首选正确解若追求更优时间复杂度可参考第 6 节的进阶优化思路。6. 进阶优化思路按余数分组的增量式滑动窗口原题解的基础版本每移动一个起始位置就重建整窗口的词频表存在大量重复切片与重复计数。可以沿两条主线继续优化按起始位置对word_length取模分组余数分桶由于所有单词等长从位置0, 1, ..., word_length - 1出发的窗口序列相互独立。对每个余数 $r \in [0, word_length)$以r为起点、word_length为步长把s切成「单词序列」然后在该序列上维护一个长度固定为word_count的滑动窗口。增量维护词频与匹配计数valid右移右边界时加入一个新单词、左移左边界时移出一个旧单词只对进出单词更新计数。若某单词的当前计数恰好等于目标计数则valid 1从恰好相等变为不等则valid - 1当valid len(target_count)时窗口匹配成功。这种写法将每次窗口移动的代价从 $O(m \times k)$ 降为 $O(k)$整体时间复杂度可达 $O(n \times k)$。这一「哈希表 valid匹配计数」的增量比较技巧与本仓库中 0567. 字符串的排列 和 0438. 找到字符串中所有字母异位词 两题的题解思路完全同源可以对照阅读形成「定长窗口 词频增量比较」的方法论沉淀。7. 相关题目串联滑动窗口家族本题属于「固定长度滑动窗口 哈希表词频比较」这一经典题型。在 AlgoNote 的题解索引见 00_05_solutions_list.md中可以找到同一家族的其他题目建议按顺序刷透题目难度核心标签题解位置0003. 无重复字符的最长子串0030. 串联所有单词的子串0076. 最小覆盖子串0438. 找到字符串中所有字母异位词中等哈希表、字符串、滑动窗口find-all-anagrams-in-a-string.md0567. 字符串的排列中等哈希表、双指针、字符串、滑动窗口permutation-in-string.md其中 0567 与 0438 是「字符级」的词频窗口问题本题则是「单词级」的词频窗口问题——窗口的切片粒度从单个字符放大到定长单词解题框架完全一致体现了滑动窗口思想在不同粒度数据上的迁移能力。8. 小结问题本质串联子串 定长窗口内按单词粒度切分后的词频与words词频完全一致核心工具固定长度滑动窗口窗口大小 word_length × word_count 哈希表词频统计关键边界空输入、len(s) total_length、words内重复单词计数而非去重性能基线朴素版 $O(n \times m \times k)$ 时间、$O(m \times k)$ 空间进阶版可按余数分组 valid增量计数优化至 $O(n \times k)$。建议在理解朴素版正确性的基础上动手实现进阶优化版并对照 01_16_array_sliding_window.md 的固定窗口代码模板与 03_06_hash_table.md 的哈希表原理把「定长窗口 词频比较」这套组合拳彻底内化。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐10分钟跑通离线翻译Argos Translate 从零到可用指南10分钟跑通离线翻译Argos Translate 从零到可用指南 Argos Translate 是一个用 Python 编写的开源离线翻译库基于 Ope人工智能NLP本地部署LeetCode 解题之路30. 串联所有单词的子串哈希表 固定窗口解法全解析LeetCode 解题之路30. 串联所有单词的子串哈希表 固定窗口解法全解析 本篇技术指南以 LeetCode 第 30 题「串联所有单词的子串」为文档教程知识库AlgoNote 算法通关手册0076. 最小覆盖子串哈希表 滑动窗口困难题精讲AlgoNote 算法通关手册0076. 最小覆盖子串哈希表 滑动窗口困难题精讲 本文是「算法通关手册」AlgoNote 仓库 0076. 最小覆教程文档知识库上一篇lovelace-wallpanel终极Home Assistant壁挂面板屏保解决方案下一篇终极指南DragGAN错误处理机制详解——从异常捕获到用户友好提示创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 AlgoNote 算法通关手册：LeetCode 0030「串联所有单词的子串」——滑动窗口 + 哈希表完整题解
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是 AlgoNote「算法通关手册」中 LeetCode 0030. 串联所有单词的子串与哈希表基础文档展开原理讲解。读完本文你将掌握如何把「单词全排列匹配」问题等价转化为「定长窗口内词频统计」问题以及用哈希表实现 $O(1)$ 词频比较的关键技巧。1. 题目概述1.1 题目大意给定一个字符串s和一个字符串数组words其中words中所有字符串长度相同。s中的「串联子串」是指一个包含words中所有字符串、以任意顺序排列连接起来的子串。例如若words [ab,cd,ef]那么abcdef、abefcd、cdabef、cdefab、efabcd、efcdab都是串联子串而acdbef不是因为它不是任何words排列的连接。要求返回所有串联子串在s中的开始索引答案顺序不限。1.2 数据范围题目约束$1 \le s.length \le 10^4$$1 \le words.length \le 5000$$1 \le words[i].length \le 30$words[i]与s仅由小写英文字母组成。1.3 示例分析示例 1输入s barfoothefoobarman, words [foo,bar] 输出[0,9] 解释words.length 2 且 words[i].length 3因此串联子串长度必须为 6。 - 子串 barfoo 起始于位置 0是 [bar,foo] 顺序排列的连接 - 子串 foobar 起始于位置 9是 [foo,bar] 顺序排列的连接。 输出顺序无关紧要返回 [9,0] 同样正确。示例 2输入s wordgoodgoodgoodbestword, words [word,good,best,word] 输出[] 解释words.length 4 且 words[i].length 4串联子串长度必须为 16。 s 中不存在长度为 16 且等于 words 任意排列连接的子串返回空数组。2. 核心思想固定长度滑动窗口 哈希表词频比较2.1 关键观察全排列匹配等价于词频匹配直接枚举words的所有排列再在s中查找是不可行的——words.length最大可达 5000全排列数量是阶乘级爆炸。这里需要抓住问题的两个结构特性窗口长度固定所有单词等长因此任一串联子串的长度必然等于 $word_length \times word_count$每个单词长度 × 单词个数。这个长度是常量与排列顺序无关。匹配等价于词频相等串联子串是words中所有单词各取一次、以任意顺序拼接的结果。只要一个窗口按单词长度切分后每种单词的出现次数恰好等于words中该单词的出现次数它就是一个串联子串——顺序完全由词频决定无需关心排列。于是「找全排列」这一 NP 式的枚举问题被降维成了「固定长度窗口内的词频对比」问题这正是本仓库固定长度滑动窗口章节所描述的标准应用场景窗口大小固定用于统计或查找长度为 $k$ 的区间性质。2.2 哈希表的作用$O(1)$ 词频比较词频对比使用哈希表完成以单词为键key、出现次数为值value。哈希表通过哈希函数 $Hash(key)$ 将键映射到存储位置实现高效插入与查找原理详见哈希表基础文档。Python 中直接用dict即可两个字典的相等比较current_count target_count会逐一比对键与值且仅在键集合完全一致时才相等天然满足「词频完全匹配」的语义。3. 算法步骤详解步骤 1计算窗口大小串联子串总长度$$total_length word_length \times word_count$$其中word_length len(words[0])题目保证所有单词等长word_count len(words)。步骤 2构建目标词频哈希表target_count遍历words统计每个单词出现次数。注意words中可能存在重复单词如示例 2 中的word出现两次因此必须用计数而非集合去重。步骤 3滑动窗口逐一切片检查从s的每个可能起始位置start范围0到len(s) - total_length出发截取长度为total_length的窗口子串按word_length为步长将窗口切成word_count个单词用哈希表统计这些单词的出现次数current_count。步骤 4匹配判断若current_count target_count则当前窗口是串联子串将start加入结果数组。边界处理若s、words或words[0]为空直接返回空列表若len(s) total_length窗口根本无法放下直接返回空列表。4. 完整代码实现思路 1滑动窗口 哈希表class Solution: def findSubstring(self, s: str, words: List[str]) - List[int]: 找到所有串联子串的起始位置 if not s or not words or not words[0]: return [] # 获取基本参数 word_length len(words[0]) # 每个单词的长度 word_count len(words) # 单词数量 total_length word_length * word_count # 串联子串的总长度 # 如果字符串长度小于串联子串长度直接返回空列表 if len(s) total_length: return [] # 构建目标单词计数哈希表 target_count {} for word in words: target_count[word] target_count.get(word, 0) 1 result [] # 遍历所有可能的起始位置 for start in range(len(s) - total_length 1): # 获取当前窗口的子串 window s[start:start total_length] # 将窗口按单词长度分割 window_words [] for i in range(0, total_length, word_length): word window[i:i word_length] window_words.append(word) # 统计当前窗口的单词出现次数 current_count {} for word in window_words: current_count[word] current_count.get(word, 0) 1 # 检查是否匹配目标计数 if current_count target_count: result.append(start) return result代码要点说明dict.get(word, 0) 1是 Python 中简洁的计数惯用法等价于「存在则累加、不存在则置 1」与collections.Counter效果一致但零依赖range(0, total_length, word_length)以单词长度为步长完成窗口切片切出的单词数恰好等于word_count两个dict直接比较会同时校验键集合与每个键对应的值这里恰好实现了「词频完全一致」的判定无需手写逐键循环。5. 复杂度分析维度复杂度说明时间复杂度$O(n \times m \times k)$其中 $n$ 为s的长度$m$ 为words的长度$k$ 为每个单词的长度。需要检查 $O(n)$ 个起始位置每个位置需切分并统计 $O(m)$ 个单词每个单词的切片与比较开销为 $O(k)$空间复杂度$O(m \times k)$存储目标词频哈希表与当前窗口词频哈希表各含至多 $m$ 个键、每键长度为 $k$在本题数据范围$n \le 10^4$、$m \le 5000$、$k \le 30$下该朴素滑动窗口版本逻辑清晰、易于验证可作为面试中的首选正确解若追求更优时间复杂度可参考第 6 节的进阶优化思路。6. 进阶优化思路按余数分组的增量式滑动窗口原题解的基础版本每移动一个起始位置就重建整窗口的词频表存在大量重复切片与重复计数。可以沿两条主线继续优化按起始位置对word_length取模分组余数分桶由于所有单词等长从位置0, 1, ..., word_length - 1出发的窗口序列相互独立。对每个余数 $r \in [0, word_length)$以r为起点、word_length为步长把s切成「单词序列」然后在该序列上维护一个长度固定为word_count的滑动窗口。增量维护词频与匹配计数valid右移右边界时加入一个新单词、左移左边界时移出一个旧单词只对进出单词更新计数。若某单词的当前计数恰好等于目标计数则valid 1从恰好相等变为不等则valid - 1当valid len(target_count)时窗口匹配成功。这种写法将每次窗口移动的代价从 $O(m \times k)$ 降为 $O(k)$整体时间复杂度可达 $O(n \times k)$。这一「哈希表 valid匹配计数」的增量比较技巧与本仓库中 0567. 字符串的排列 和 0438. 找到字符串中所有字母异位词 两题的题解思路完全同源可以对照阅读形成「定长窗口 词频增量比较」的方法论沉淀。7. 相关题目串联滑动窗口家族本题属于「固定长度滑动窗口 哈希表词频比较」这一经典题型。在 AlgoNote 的题解索引见 00_05_solutions_list.md中可以找到同一家族的其他题目建议按顺序刷透题目难度核心标签题解位置0003. 无重复字符的最长子串0030. 串联所有单词的子串0076. 最小覆盖子串0438. 找到字符串中所有字母异位词中等哈希表、字符串、滑动窗口find-all-anagrams-in-a-string.md0567. 字符串的排列中等哈希表、双指针、字符串、滑动窗口permutation-in-string.md其中 0567 与 0438 是「字符级」的词频窗口问题本题则是「单词级」的词频窗口问题——窗口的切片粒度从单个字符放大到定长单词解题框架完全一致体现了滑动窗口思想在不同粒度数据上的迁移能力。8. 小结问题本质串联子串 定长窗口内按单词粒度切分后的词频与words词频完全一致核心工具固定长度滑动窗口窗口大小 word_length × word_count 哈希表词频统计关键边界空输入、len(s) total_length、words内重复单词计数而非去重性能基线朴素版 $O(n \times m \times k)$ 时间、$O(m \times k)$ 空间进阶版可按余数分组 valid增量计数优化至 $O(n \times k)$。建议在理解朴素版正确性的基础上动手实现进阶优化版并对照 01_16_array_sliding_window.md 的固定窗口代码模板与 03_06_hash_table.md 的哈希表原理把「定长窗口 词频比较」这套组合拳彻底内化。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐10分钟跑通离线翻译Argos Translate 从零到可用指南10分钟跑通离线翻译Argos Translate 从零到可用指南 Argos Translate 是一个用 Python 编写的开源离线翻译库基于 Ope人工智能NLP本地部署LeetCode 解题之路30. 串联所有单词的子串哈希表 固定窗口解法全解析LeetCode 解题之路30. 串联所有单词的子串哈希表 固定窗口解法全解析 本篇技术指南以 LeetCode 第 30 题「串联所有单词的子串」为文档教程知识库AlgoNote 算法通关手册0076. 最小覆盖子串哈希表 滑动窗口困难题精讲AlgoNote 算法通关手册0076. 最小覆盖子串哈希表 滑动窗口困难题精讲 本文是「算法通关手册」AlgoNote 仓库 0076. 最小覆教程文档知识库上一篇lovelace-wallpanel终极Home Assistant壁挂面板屏保解决方案下一篇终极指南DragGAN错误处理机制详解——从异常捕获到用户友好提示创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考