每日一题 — 串联所有单词的子串

30. 串联所有单词的子串 - 力扣（LeetCode）

思路：因为words里面的每一个字符串的长度都是固定的，所以可以将题转换成字符在字符串中的所有异位词

• 设出哈希表
• 定义left和right
• 进窗口+维护count
• 判断
• 出窗口+维护count 

代码：

public List<Integer> findSubstring(String s, String[] words) {List<Integer> ret = new ArrayList<>();int len = words[0].length();int m = words.length;Map<String,Integer> hash1 = new HashMap<>();//将words中的所有字符加入到哈希表中for(String str : words){hash1.put(str,hash1.getOrDefault(str,0)+1);}//进窗口的次数(len 次)for(int i = 0; i < len; i++){Map<String,Integer> hash2 = new HashMap<>();for(int left = i, right = i, count = 0; right + len <= s.length(); right += len){//进窗口String in = s.substring(right,right+len);hash2.put(in,hash2.getOrDefault(in,0)+1);//维护countif(hash2.get(in) <= hash1.getOrDefault(in,0)){count++;}//判断if(right - left + 1 > m*len){//出窗口String out = s.substring(left,left+len);//维护countif(hash2.get(out) <= hash1.getOrDefault(out,0)){count--;}hash2.put(out,hash2.get(out)-1);left+=len;}if(m == count){ret.add(left);}}}return ret;}