15.LeetCode 30. 串联所有单词的子串（Java）：滑动窗口+哈希表详解

目录1. 题目解析2. 讲解算法原理3. 代码实现完整保留https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/1. 题目解析题目串联所有单词的子串给定一个字符串s和一个单词数组wordswords中所有单词长度相同。要求找出s中串联子串的起始位置——即包含words中所有单词顺序不限连续拼接而成的子串。示例1输入s barfoothefoobarman,words [foo,bar]输出[0,9]解释words长度为2words[0]长度为3故子串长度需为2×36。子串barfoo从位置0开始是[bar,foo]的排列子串foobar从位置9开始是[foo,bar]的排列。返回顺序无关如[9,0]也可。2. 讲解算法原理解法滑动窗口 哈希表参考类似题目如438. 找出所有的字母异位词本题核心是用滑动窗口覆盖所有单词的拼接并通过哈希表统计单词频次。关键思路哈希表用hash1存words中每个单词的出现次数用hash2存滑动窗口内单词的出现次数。指针移动左指针left、右指针right按单词长度len移动因为单词长度固定。滑动窗口执行次数外层循环次数为len因为单词长度可能为1~len需覆盖所有可能的起始偏移。示意图理解示例s barfoothefoobarman,words [foo,bar]滑动窗口的移动以及hash1words频次、hash2窗口内频次的对比。3. 代码实现完整保留class Solution { public ListInteger findSubstring(String s, String[] words) { ListInteger ret new ArrayListInteger(); MapString, Integer hash1 new HashMapString, Integer(); // 保存字典中所有单词的频次 for (String str : words) hash1.put(str, hash1.getOrDefault(str, 0) 1); int len words[0].length(), m words.length; for (int i 0; i len; i) { // 执行次数单词长度的循环 MapString, Integer hash2 new HashMapString, Integer(); // 保存窗口内所有单词的频次 for (int left i, right i, count 0; right len s.length(); right len) { // 进窗口 维护 count String in s.substring(right, right len); hash2.put(in, hash2.getOrDefault(in, 0) 1); if (hash2.get(in) hash1.getOrDefault(in, 0)) count; // 出窗口条件窗口长度超过 单词总长度len*m if (right - left 1 len * m) { String out s.substring(left, left len); if (hash2.get(out) hash1.getOrDefault(out, 0)) count--; hash2.put(out, hash2.get(out) - 1); left len; } // 更新结果count等于单词总数m时记录left if (count m) ret.add(left); } } return ret; } }