算法15，滑动窗口，串联所有单词的字串

这是一道关于滑动窗口算法的编程题目核心是解决“找到字符串中包含所有指定单词的子串的起始索引”问题。以下是对该问题的解答和解题思路问题描述给定一个字符串s和一个字符串数组words其中words中的所有单词长度相同。需要找到s中所有起始索引使得从该索引开始的子串是由words中所有单词以任意顺序连接而成每个单词恰好出现一次。返回这些起始索引的列表。示例输入s barfoothefoobarman,words [foo, bar]输出[0, 9]解释从索引0开始的子串barfoo和从索引9开始的子串foobar都包含foo和bar各一次解题思路哈希表记录单词频次首先使用哈希表wordCount记录words中每个单词的出现次数因为单词可能重复。滑动窗口扫描由于所有单词长度相同设为wordLen总子串长度为totalLen words.length * wordLen。在字符串s上从左到右遍历每个可能的起始位置从0到s.length() - totalLen对每个起始位置使用滑动窗口检查子串。窗口维护对于当前起始位置i初始化一个哈希表seen记录窗口中单词的频次并移动right指针步进wordLen长度截取子串。每次截取一个长度为wordLen的单词sub检查是否在wordCount中如果不在说明当前窗口无效跳出循环。如果在更新seen中该单词的频次。如果seen中该单词频次超过wordCount中的频次说明窗口无效需要收缩左指针left调整。当窗口中单词数量匹配words的长度时记录起始索引i。优化由于单词长度固定滑动窗口只需扫描wordLen次分别以0, 1, ..., wordLen-1为起始偏移以减少重复计算。步骤详解计算wordLen单词长度和totalLen总长度。构建哈希表wordCount存储words中单词频次。循环wordLen次每次从偏移量start开始滑动窗口初始化left startright start哈希表seen为空计数器count记录窗口中有效单词数。当right wordLen s.length()时循环截取单词word s.substring(right, right wordLen)。如果word不在wordCount中重置窗口left right wordLen清空seencount 0。否则更新seen中word的频次。如果seen.get(word) wordCount.get(word)增加count否则收缩left指针直到频次匹配。当count等于words.length时表示找到一个有效子串记录起始索引left然后移动left指针继续检查。每次移动right指针步进wordLen。返回所有记录的起始索引。代码示例Javaimport java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Solution { public ListInteger findSubstring(String s, String[] words) { ListInteger result new ArrayList(); if (s null || s.length() 0 || words null || words.length 0) { return result; } int wordLen words[0].length(); int totalLen words.length * wordLen; int sLen s.length(); // 哈希表记录 words 中单词频次 MapString, Integer wordCount new HashMap(); for (String word : words) { wordCount.put(word, wordCount.getOrDefault(word, 0) 1); } // 滑动窗口扫描 for (int i 0; i wordLen; i) { int left i, right i; MapString, Integer seen new HashMap(); int count 0; while (right wordLen sLen) { String word s.substring(right, right wordLen); right wordLen; if (wordCount.containsKey(word)) { seen.put(word, seen.getOrDefault(word, 0) 1); if (seen.get(word) wordCount.get(word)) { count; } else { // 收缩窗口直到频次匹配 while (seen.get(word) wordCount.get(word)) { String leftWord s.substring(left, left wordLen); seen.put(leftWord, seen.get(leftWord) - 1); if (seen.get(leftWord) wordCount.getOrDefault(leftWord, 0)) { count--; } left wordLen; } } // 检查是否找到有效子串 if (count words.length) { result.add(left); // 移动左指针继续搜索 String leftWord s.substring(left, left wordLen); seen.put(leftWord, seen.get(leftWord) - 1); count--; left wordLen; } } else { // 当前单词无效重置窗口 seen.clear(); count 0; left right; } } } return result; } }复杂度分析时间复杂度O(wordLen * (sLen / wordLen))即 O(sLen)其中 sLen 是字符串 s 的长度wordLen 是单词长度。滑动窗口扫描了整个字符串。空间复杂度O(words.length)用于存储哈希表。总结这道题的关键在于利用哈希表记录单词频次并结合滑动窗口高效检查子串。通过固定单词长度我们可以将问题转化为多次滑动窗口扫描确保每个可能起始位置都被覆盖。图片中的代码片段展示了哈希表和循环的基本思路但以上代码提供了完整实现。