算法思想（中文解釋）

這道題目要求我們在字符串 s 中找到所有子串，這些子串是字符串數組 words 中所有單詞的串聯，并且每個單詞只能使用一次，且順序可以任意。下面是代碼的算法思想：

---

1. 核心思路

分解問題：

• 因為每個單詞長度相同，我們可以使用一個滑動窗口（Sliding Window）來檢查所有可能的子串。
• 判斷一個子串是否是所有單詞的串聯，可以通過比較單詞的頻次。

---

2. 步驟講解

（1）初始化：

• 單詞長度：用 wordLength 表示 words 中每個單詞的長度（因為題目保證它們長度相同）。
• 總串聯長度：totalLength = wordLength * words.length，因為子串的長度一定是所有單詞的長度之和。
• 構造單詞頻次表：用 wordMap 記錄 words 中每個單詞的出現次數，便于后續比較。

（2）滑動窗口遍歷：

• 從字符串 s 的每個位置開始，以長度為 totalLength 的窗口進行檢查：
  • 提取窗口中的子串 sub。
  • 檢查這個子串是否包含了 words 中所有單詞且頻次正確。

（3）子串驗證：

• 對于窗口中的子串 sub，將其按照 wordLength 分割成一個個小單詞。
• 檢查這些小單詞是否在 wordMap 中，并驗證它們的出現頻次是否超出限制：
  • 如果某個單詞不在 wordMap 中，立即返回 false；
  • 如果某個單詞出現的次數超過了在 wordMap 中的次數，也返回 false。
• 如果所有單詞驗證通過，則說明當前窗口位置是符合要求的，記錄下起始索引。

---

3. 時間復雜度分析

1. 構造單詞頻次表：O(m)，其中 m 是 words 的長度（即單詞個數）。
2. 滑動窗口遍歷：外層遍歷最多需要 n - totalLength + 1 次，n 是字符串 s 的長度。
3. 驗證子串：每次驗證需要遍歷窗口中的所有單詞，復雜度為 O(m * wordLength)。

因此，總復雜度為：
[ O((n - totalLength + 1) \cdot m \cdot wordLength) ]
通常可以簡化為 O(n * m)，適用于 s 較長和 words 較短的場景。

---

4. 代碼邏輯解釋

主函數：

1. wordMap：統計 words 中每個單詞的出現頻次。
2. 滑動窗口遍歷：通過 for 循環，遍歷從 0 到 s.length() - totalLength 的所有可能起始位置。
3. 子串驗證：調用輔助函數 isValid() 檢查是否符合要求。

輔助函數 isValid：

1. 將子串 sub 分割成長度為 wordLength 的小單詞。
2. 使用 seen 哈希表記錄窗口內每個單詞的頻次。
3. 與 wordMap 進行比較，判斷是否匹配。

---

5. 關鍵優化點

1. 滑動窗口：避免暴力檢查所有子串，只檢查可能的窗口，減少不必要的計算。
2. 哈希表：使用 wordMap 和 seen 快速判斷頻次關系，而不是逐一比較。
3. 提前退出：在驗證過程中，一旦發現不匹配的單詞，立即退出驗證，避免冗余計算。

---

6. 適用場景

該算法非常適用于以下情況：

• 單詞長度固定，字符串較長。
• words 中的單詞個數適中（否則頻次表的維護開銷較大）。

通過滑動窗口和哈希表的結合，這個算法能夠高效解決題目要求。

java solution

class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> result = new ArrayList<>();if(s == null || s.length() == 0 || words.length == 0 || words == null) return result;//初始化輔助變量int wordsLength = words.length;int wordLength = words[0].length();int totalLength = wordLength * wordsLength;//創建頻率統計哈希表Map<String, Integer> freq = new HashMap<>();for(String word:words) {freq.put(word, freq.getOrDefault(word, 0) + 1);}//變量字符串sfor(int i = 0; i <= s.length() - totalLength; i++) {//首先獲取窗口內的子串String sub = s.substring(i, i + totalLength); //substring 是左閉右開//然后驗證此時窗口內的子串if(isValid(sub, freq, wordLength)) {result.add(i);}}return result;}private boolean isValid(String sub, Map<String, Integer> freq, int wordLength) {Map<String, Integer> seen = new HashMap<>(); //存儲子串中的單詞頻次for(int j = 0; j < sub.length(); j += wordLength) {//提取子串中的單詞String word = sub.substring(j, j + wordLength);if(!freq.containsKey(word)) { //如果這個單詞不在freq頻率表中,return false;}seen.put(word, seen.getOrDefault(word, 0) + 1); //更新seen中的頻次if(seen.get(word) > freq.get(word)) { //如果頻次超過freq的限制return false; }}return true;}
}

182 個測試用例通過了 181 個，被全 a 的測試用例卡住了(超時)，