哈希算法题目：串联所有单词的子串

题目描述：
给定一个字符串 s 和一个字符串数组 words。words 中所有字符串长度相同。s 中需要找到一个子串，这个子串恰好是由 words 中所有字符串串联形成的（每个字符串恰好出现一次，串联顺序不限）。返回所有符合条件的子串的起始索引。

解题过程：

1. 问题理解：

   • 我们需要在字符串s中找到一个连续子串
   • 这个子串必须包含words数组中所有的字符串，每个字符串恰好出现一次
   • words中所有字符串长度相同，设为word_len
   • 需要返回所有满足条件的子串的起始位置

2. 基本思路分析：

   • 由于words中所有单词长度相同，我们可以将问题分解
   • 总子串长度应该是：word_len × words数组长度
   • 我们需要检查s中所有可能长度为word_len × words.length的子串
   • 对于每个候选子串，检查是否能被拆分成words中的所有单词

3. 哈希表的使用：

   • 用哈希表记录words中每个单词应该出现的次数
   • 对于每个候选子串，用另一个哈希表记录实际出现的单词次数
   • 比较两个哈希表是否完全相同

4. 滑动窗口实现：

   • 由于单词长度固定，我们可以按单词长度进行多次遍历
   • 每次遍历从不同的起始位置开始（0到word_len-1）
   • 使用滑动窗口，窗口大小为words中单词的总长度

5. 具体步骤：
   a. 特殊情况处理：如果s为空或words为空，直接返回空结果
   b. 计算单词长度word_len和总长度total_len
   c. 创建目标哈希表word_count，记录words中每个单词的出现次数
   d. 从0到word_len-1分别作为起始位置进行遍历
   e. 在每个起始位置，使用左右指针维护滑动窗口
   f. 移动右指针，每次取一个单词，更新当前窗口的单词计数
   g. 如果当前单词不在words中，重置窗口
   h. 如果窗口大小超过total_len，移动左指针缩小窗口
   i. 当窗口大小等于total_len且单词计数匹配时，记录起始位置

6. 优化技巧：

   • 当遇到不在words中的单词时，可以直接跳过整个区间
   • 使用计数器记录匹配的单词数量，避免每次比较整个哈希表
   • 通过记录有效单词数量来快速判断是否找到解

7. 复杂度分析：

   • 时间复杂度：O(n × word_len)，其中n是字符串s的长度
   • 空间复杂度：O(m × word_len)，其中m是words数组的长度

这个算法通过巧妙的滑动窗口和单词长度固定的特性，有效地解决了字符串匹配问题，避免了暴力解法的高时间复杂度。