力扣（串联所有单词的子串）
串联所有单词的子串问题：多滑动窗口与哈希表的实战应用。
一、题目分析
（一）问题定义
给定字符串 s 和字符串数组 words（words 中所有单词长度相同 ），找出 s 中所有“串联子串”的起始索引。串联子串指包含 words 中所有单词（任意顺序连接）的子串。例如 words = ["ab","cd","ef"] 时，"abcdef"、"abefcd" 等符合要求，而顺序混乱或缺失单词的子串则不符合。
（二）核心挑战
- 精确匹配：需确保子串包含
words中所有单词，且数量一致，顺序不限。 - 高效遍历：
s可能较长，words单词数量和长度各异，需避免暴力枚举所有可能子串（时间复杂度过高 ）。 - 时间复杂度控制：题目要求高效算法，需利用哈希表和滑动窗口思想，将时间复杂度优化到可接受范围。
二、算法思想：多滑动窗口 + 哈希表协同
（一）哈希表的作用
- 词频统计：用哈希表
wordMap统计words中各单词的出现次数，作为匹配依据。 - 窗口词频对比：在滑动窗口过程中，维护当前窗口内的单词词频哈希表（
windows数组中的每个Map），与wordMap对比，判断窗口是否为串联子串。
（二）多滑动窗口的设计
由于 words 中单词长度固定（设为 wordLen ），子串需由连续的单词拼接而成。因此，以 wordLen 为间隔，设计 wordLen 个滑动窗口（对应不同起始偏移 ）。例如 wordLen = 3 时，窗口起始偏移为 0、1、2 ，分别处理不同起始位置的子串，确保覆盖所有可能的串联子串。
（三）滑动窗口的移动策略
- 初始化窗口：对每个起始偏移
i（0 <= i < wordLen），初始化一个窗口，截取s中对应位置的所有单词（按wordLen分割 ），统计词频存入windows[i]。 - 动态移动窗口：窗口初始化后，以
wordLen为步长向右滑动。每次滑动时，移除窗口左侧的旧单词，加入右侧的新单词，更新windows[winIndex]的词频，再与wordMap对比，判断是否为串联子串。
三、代码实现与详细注释
class Solution {public List<Integer> findSubstring(String s, String[] words) {int wordCount = words.length;int wordLen = words[0].length();int sLen = s.length();List<Integer> res = new ArrayList<>();//如果words的长度大于s的长度,则不可能有子串if (sLen < wordCount * wordLen || s == null || sLen == 0 || words == null || wordCount == 0) {return res;}//将word置入wordMap,用于比对和计数Map<String, Integer> wordMap = new HashMap<>();for (String word : words) {//如果word存在就在原有的数量上+1不存在为0+1;wordMap.put(word, 1 + wordMap.getOrDefault(word, 0));}//采用多滑动窗口的方式,一个下标表示一个滑动窗口Map<String, Integer>[] windows;windows = new HashMap[wordLen];//初始化多滑动窗口 i为windows中的每一个窗口下标//wordCount*wordLen是滑动窗口的大小//i+wordCount*wordLen确保当前起始位置 i 之后，存在足够长度的子串for (int i = 0; i < wordLen && i + wordCount * wordLen <= sLen; i++) {// 在外层循环中初始化每个窗口的Mapwindows[i] = new HashMap<>();//提取对应滑动窗口内的所有单词/*j=i,例:i=0即该滑动窗口是0偏移量的单词i=1即该滑动窗口是1偏移量的单词*///退出条件:j要保持在对应滑动窗口的大小中//j+=wordLen: 每次递增一个单词的长度 for (int j = i; j < i + wordCount * wordLen; j += wordLen) {String subStr = s.substring(j, j + wordLen); // j是当前单词的起始索引//对字符串进行截取,截取为一个单词一个单词windows[i].put(subStr, 1 + windows[i].getOrDefault(subStr, 0));}//判断每一个滑动窗口有没有窗口已经是子串if (windows[i].equals(wordMap)) {res.add(i);}}//移动窗口//i代表窗口的左边界//在上面已经对窗口进行初始化,起始位置从第一个窗口的下一个单词长度开始//i+wordCount*wordLen<=sLen:确保当前位置i之后有足够的长度容纳整个窗口for (int i = wordLen; i + wordCount * wordLen <= sLen; i++) {//滑动窗口的相对位置int winIndex = i % wordLen;// s.substring(i,wordLen+j)// 截取左侧单词（起始位置：i - wordLen，长度：wordLen）String pervWord = s.substring(i - wordLen, (i - wordLen) + wordLen);// 截取右侧新单词（起始位置：nextWordStart，长度：wordLen）int nextWordStart = i + (wordCount - 1) * wordLen;String nextWord = s.substring(nextWordStart, nextWordStart + wordLen);//删除左侧单词:如果在哈希表中值>1则这个word出现了1次以上,要在原值的基础上-1,而不是直接删除if(windows[winIndex].get(pervWord)>1){windows[winIndex].put(pervWord,windows[winIndex].get(pervWord)-1);}else{windows[winIndex].remove(pervWord); }//加入右侧单词windows[winIndex].put(nextWord, 1 + windows[winIndex].getOrDefault(nextWord, 0));//判断每一个滑动窗口有没有窗口已经是子串if (windows[winIndex].equals(wordMap)) {res.add(i);}}return res;}
}
（一）代码流程拆解
- 初始化与边界处理：
- 计算
wordCount（单词数量 ）、wordLen（单词长度 ）、sLen（s长度 ）。 - 若
s长度不足容纳words所有单词拼接（sLen < wordCount * wordLen），直接返回空结果。
- 计算
- 构建
wordMap：统计words中各单词的词频，用于后续匹配。 - 多滑动窗口初始化：
- 针对每个起始偏移
i（0 ~ wordLen-1），初始化窗口的词频表windows[i]。 - 截取
s中对应窗口的所有单词，统计词频。 - 若窗口词频与
wordMap匹配，记录起始索引i。
- 针对每个起始偏移
- 滑动窗口处理：
- 从
i = wordLen开始，继续滑动窗口。 - 计算当前窗口的偏移索引
winIndex（i % wordLen）。 - 移除窗口左侧旧单词，更新词频；加入右侧新单词，更新词频。
- 对比当前窗口词频与
wordMap，匹配则记录起始索引i。
- 从
（二）关键逻辑解析
- 多窗口设计：因单词长度固定，不同起始偏移（
0 ~ wordLen-1）的子串需独立处理。例如wordLen=3时，起始偏移0、1、2对应子串起始为0、1、2，需分别用窗口覆盖。 - 窗口词频更新：滑动时，通过“移除左侧旧单词、加入右侧新单词”的方式，避免重复截取子串（优化时间复杂度 ）。利用哈希表的增删操作，高效维护窗口内的词频。
- 匹配判断：每次窗口更新后，直接对比
windows[winIndex]与wordMap，利用哈希表的equals方法快速判断是否匹配。
三、复杂度分析
（一）时间复杂度
- 初始化多窗口：共
wordLen个窗口，每个窗口截取wordCount个单词（每个单词截取时间为O(wordLen)），总时间复杂度为O(wordLen * wordCount * wordLen) = O(wordLen² * wordCount)。 - 滑动窗口处理：共
sLen - wordCount * wordLen次滑动（近似O(sLen)），每次滑动涉及哈希表的增删查操作（均为O(1)，单词数量固定 ），总时间复杂度为O(sLen)。 - 整体时间复杂度：
O(wordLen² * wordCount + sLen)。因wordLen和wordCount通常远小于sLen，可近似认为是O(sLen)，满足题目高效要求。
（二）空间复杂度
- 哈希表存储：
wordMap存储wordCount个单词的词频，windows数组存储wordLen个窗口的词频（每个窗口最多wordCount个单词 ），空间复杂度为O(wordCount + wordLen * wordCount) = O(wordLen * wordCount)。 - 额外空间：结果列表
res存储符合条件的起始索引，最多O(sLen / wordLen)个元素。整体空间复杂度为O(wordLen * wordCount + sLen / wordLen)，可接受。
串联所有单词的子串问题，通过多滑动窗口 + 哈希表的协同策略，巧妙解决了精确匹配与高效遍历的难题。多窗口覆盖不同起始偏移，确保不遗漏可能的子串；哈希表实现词频快速统计与对比，优化匹配效率。