LeetCode代码分析——30.|LeetCode代码分析——30. Substring with Concatenation of All Words（理解滑动窗口） LeetCode代码分析——30.Substrin

题目描述 You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
给定一个String s和一个单词的数组words，数组里面的单词长度相等，从s中找出字符串，使得数组中的每个单词刚好都出现过一次，也就是字符串是数组中单词的一个全排列。

Example
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

思路分析注意题目中的条件，words数组中的单词长度相等，如果没有这个条件这道题还挺复杂的。如果长度相等的话形如barfoofoothefoobarman的字符串就可以被三等分

bar foo foo the foo bar man
b arf oof oot hef oob arm an
ba rfo ofo oth efo oba rma n

三个为一组进行分组，总共三种可能的分组。同时注意条件，words数组中的单词可以重复，会出现["foo","bar","foo"]的情况，这种情况也需要匹配到两个foo，即foobarfoo这样的子串。
因此需要先用一个Map wordMap来记录下words数组中每个单词的次数，例如本例中就是
bar: 1
foo: 1
然后分别对以上三种分组方式进行分析，遍历采用left和right两个指针，对s中的每个单词和words数组中的进行匹配，同时用tempMap记录当前left和right指针之间的各个单词的数量（用来和wordMap比较）。
算法的执行过程如图。

LeetCode代码分析——30.|LeetCode代码分析——30. Substring with Concatenation of All Words（理解滑动窗口）

文章图片
算法执行逻辑
left和right指针组成了一个滑动窗口，通过tempMap 忠实记录left和right指针之间的单词匹配计数（只要left right指针发生移动就立刻更新），在发现某个单词（如foo）超过了模板wordMap中的计数，则滑动窗口左边界逐渐右移，同时更新tempMap，直到多余的foo被弹了出去，再继续右移右指针进行操作。
核心在于理解为什么要用滑动窗口，本题是通过滑动窗口+记录用的Map来保证窗口内的单词数和要求的个数统一。（有些类似于网络的滑动窗口协议，为了保持帧的传输顺序和传输个数，也是说在窗口里的一定要是要求的结果的子集，窗口里不允许进入不符合要求的元素） 【LeetCode代码分析——30.|LeetCode代码分析——30. Substring with Concatenation of All Words（理解滑动窗口）】
代码实现

class Solution { public List findSubstring(String s, String[] words) { List result = new ArrayList<>(); Map wordMap = new HashMap<>(); for (String word : words) { if (wordMap.containsKey(word)) { wordMap.put(word, wordMap.get(word) + 1); } else { wordMap.put(word, 1); } }if (s.length() == 0 || words.length == 0) { return result; }int wordLen = words[0].length(); int totalLen = wordLen * words.length; for (int i = 0; i < words[0].length(); i++) { int left = i; int right = i; Map tempMap = new HashMap<>(); while (right + wordLen <= s.length()) { // 滑窗右侧扩张 String temp = s.substring(right, right + wordLen); right += wordLen; if (wordMap.containsKey(temp)) { if (tempMap.containsKey(temp)) { tempMap.put(temp, tempMap.get(temp) + 1); } else { tempMap.put(temp, 1); } while (tempMap.get(temp) > wordMap.get(temp)) { // temp单词匹配过多，滑窗左边逐渐缩小，直到弹出多余的单词 String leftStr = s.substring(left, left + wordLen); tempMap.put(leftStr, tempMap.get(leftStr) - 1); left += wordLen; } if (right - left == totalLen) { // 通过滑窗大小来判断是否匹配成功 result.add(left); } } else { // 没有匹配到，滑窗缩小为0，从right部分重新开始 tempMap = new HashMap<>(); left = right; } } }return result; } }