算法思路

1. 哈希映射统计：首先使用哈希映射（HashMap）统计words数组中每个单词出现的次数。

2. 滑动窗口：由于所有单词的长度相同，我们可以使用滑动窗口的方式，以单词的长度为步长在原字符串s上滑动，检查每个可能的窗口。

3. 匹配验证：对于每个窗口，使用另一个哈希映射统计窗口中每个单词的出现次数，然后与words的哈希映射进行比较，看是否完全匹配。

4. 记录起始位置：如果一个窗口完全匹配，记录该窗口的起始位置。

5. 优化：为了减少不必要的检查，我们只需要在0到wordLength-1的范围内开始滑动窗口，其中wordLength是数组words中单词的长度。

   
   import java.util.ArrayList;
   import java.util.HashMap;
   import java.util.List;
   import java.util.Map;
   
   public class Solution {
       public List<Integer> findSubstring(String s, String[] words) {
           int wordLength = words[0].length();
           int allWordsLength = words.length * wordLength;
           Map<String, Integer> wordMap = new HashMap<>();
           List<Integer> result = new ArrayList<>();
   
           for (String word : words) {
               wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
           }
   
           for (int i = 0; i < wordLength; i++) {
               for (int j = i; j <= s.length() - allWordsLength; j += wordLength) {
                   Map<String, Integer> seen = new HashMap<>();
                   int k = 0;
                   while (k < words.length) {
                       String word = s.substring(j + k * wordLength, j + (k + 1) * wordLength);
                       if (wordMap.containsKey(word)) {
                           seen.put(word, seen.getOrDefault(word, 0) + 1);
                           if (seen.get(word) > wordMap.get(word)) break;
                       } else {
                           break;
                       }
                       k++;
                   }
                   if (k == words.length) result.add(j);
               }
           }
   
           return result;
       }
   }

   算法解析

   这个算法的关键在于如何有效地利用哈希映射来减少不必要的比较。通过维护一个滑动窗口，并在每次迭代中更新这个窗口内单词的出现次数，我们可以有效地判断当前窗口是否满足条件。

   此外，通过分步骤处理，即先统计words数组中单词的出现次数，然后通过滑动窗口检查每个子串，这种方法既清晰又易于实现。

   示例和测试

   以s = "barfoothefoobarman", words = ["foo","bar"]为例，我们的函数应该返回[0,9]。这是因为在s中，从索引0开始的子串"barfoo"和从索引9开始的子串"foobar"恰好由words中的所有单词串联形成。

   总结

   这道题目展示了在字符串处理和算法设计中哈希映射的强大应用。通过巧妙地利用哈希映射来追踪和比较子串中单词的出现次数，我们能够有效地解决复杂的字符串匹配问题。

 觉得写的不错的朋友，请点点赞！万分感谢