串聯所有單詞的子串問題：多滑動窗口與哈希表的實戰應用。
一、題目分析
（一）問題定義
給定字符串 s 和字符串數組 words（words 中所有單詞長度相同 ），找出 s 中所有“串聯子串”的起始索引。串聯子串指包含 words 中所有單詞（任意順序連接）的子串。例如 words = ["ab","cd","ef"] 時，"abcdef"、"abefcd" 等符合要求，而順序混亂或缺失單詞的子串則不符合。
（二）核心挑戰
- 精確匹配：需確保子串包含
words中所有單詞，且數量一致，順序不限。 - 高效遍歷：
s可能較長，words單詞數量和長度各異，需避免暴力枚舉所有可能子串（時間復雜度過高 ）。 - 時間復雜度控制：題目要求高效算法，需利用哈希表和滑動窗口思想，將時間復雜度優化到可接受范圍。
二、算法思想：多滑動窗口 + 哈希表協同
（一）哈希表的作用
- 詞頻統計：用哈希表
wordMap統計words中各單詞的出現次數，作為匹配依據。 - 窗口詞頻對比：在滑動窗口過程中，維護當前窗口內的單詞詞頻哈希表（
windows數組中的每個Map），與wordMap對比，判斷窗口是否為串聯子串。
（二）多滑動窗口的設計
由于 words 中單詞長度固定（設為 wordLen ），子串需由連續的單詞拼接而成。因此，以 wordLen 為間隔，設計 wordLen 個滑動窗口（對應不同起始偏移 ）。例如 wordLen = 3 時，窗口起始偏移為 0、1、2 ，分別處理不同起始位置的子串，確保覆蓋所有可能的串聯子串。
（三）滑動窗口的移動策略
- 初始化窗口：對每個起始偏移
i（0 <= i < wordLen），初始化一個窗口，截取s中對應位置的所有單詞（按wordLen分割 ），統計詞頻存入windows[i]。 - 動態移動窗口：窗口初始化后，以
wordLen為步長向右滑動。每次滑動時，移除窗口左側的舊單詞，加入右側的新單詞，更新windows[winIndex]的詞頻，再與wordMap對比，判斷是否為串聯子串。
三、代碼實現與詳細注釋
class Solution {public List<Integer> findSubstring(String s, String[] words) {int wordCount = words.length;int wordLen = words[0].length();int sLen = s.length();List<Integer> res = new ArrayList<>();//如果words的長度大于s的長度,則不可能有子串if (sLen < wordCount * wordLen || s == null || sLen == 0 || words == null || wordCount == 0) {return res;}//將word置入wordMap,用于比對和計數Map<String, Integer> wordMap = new HashMap<>();for (String word : words) {//如果word存在就在原有的數量上+1不存在為0+1;wordMap.put(word, 1 + wordMap.getOrDefault(word, 0));}//采用多滑動窗口的方式,一個下標表示一個滑動窗口Map<String, Integer>[] windows;windows = new HashMap[wordLen];//初始化多滑動窗口 i為windows中的每一個窗口下標//wordCount*wordLen是滑動窗口的大小//i+wordCount*wordLen確保當前起始位置 i 之后，存在足夠長度的子串for (int i = 0; i < wordLen && i + wordCount * wordLen <= sLen; i++) {// 在外層循環中初始化每個窗口的Mapwindows[i] = new HashMap<>();//提取對應滑動窗口內的所有單詞/*j=i,例:i=0即該滑動窗口是0偏移量的單詞i=1即該滑動窗口是1偏移量的單詞*///退出條件:j要保持在對應滑動窗口的大小中//j+=wordLen: 每次遞增一個單詞的長度 for (int j = i; j < i + wordCount * wordLen; j += wordLen) {String subStr = s.substring(j, j + wordLen); // j是當前單詞的起始索引//對字符串進行截取,截取為一個單詞一個單詞windows[i].put(subStr, 1 + windows[i].getOrDefault(subStr, 0));}//判斷每一個滑動窗口有沒有窗口已經是子串if (windows[i].equals(wordMap)) {res.add(i);}}//移動窗口//i代表窗口的左邊界//在上面已經對窗口進行初始化,起始位置從第一個窗口的下一個單詞長度開始//i+wordCount*wordLen<=sLen:確保當前位置i之后有足夠的長度容納整個窗口for (int i = wordLen; i + wordCount * wordLen <= sLen; i++) {//滑動窗口的相對位置int winIndex = i % wordLen;// s.substring(i,wordLen+j)// 截取左側單詞（起始位置：i - wordLen，長度：wordLen）String pervWord = s.substring(i - wordLen, (i - wordLen) + wordLen);// 截取右側新單詞（起始位置：nextWordStart，長度：wordLen）int nextWordStart = i + (wordCount - 1) * wordLen;String nextWord = s.substring(nextWordStart, nextWordStart + wordLen);//刪除左側單詞:如果在哈希表中值>1則這個word出現了1次以上,要在原值的基礎上-1,而不是直接刪除if(windows[winIndex].get(pervWord)>1){windows[winIndex].put(pervWord,windows[winIndex].get(pervWord)-1);}else{windows[winIndex].remove(pervWord); }//加入右側單詞windows[winIndex].put(nextWord, 1 + windows[winIndex].getOrDefault(nextWord, 0));//判斷每一個滑動窗口有沒有窗口已經是子串if (windows[winIndex].equals(wordMap)) {res.add(i);}}return res;}
}
（一）代碼流程拆解
- 初始化與邊界處理：
- 計算
wordCount（單詞數量 ）、wordLen（單詞長度 ）、sLen（s長度 ）。 - 若
s長度不足容納words所有單詞拼接（sLen < wordCount * wordLen），直接返回空結果。
- 計算
- 構建
wordMap：統計words中各單詞的詞頻，用于后續匹配。 - 多滑動窗口初始化：
- 針對每個起始偏移
i（0 ~ wordLen-1），初始化窗口的詞頻表windows[i]。 - 截取
s中對應窗口的所有單詞，統計詞頻。 - 若窗口詞頻與
wordMap匹配，記錄起始索引i。
- 針對每個起始偏移
- 滑動窗口處理：
- 從
i = wordLen開始，繼續滑動窗口。 - 計算當前窗口的偏移索引
winIndex（i % wordLen）。 - 移除窗口左側舊單詞，更新詞頻；加入右側新單詞，更新詞頻。
- 對比當前窗口詞頻與
wordMap，匹配則記錄起始索引i。
- 從
（二）關鍵邏輯解析
- 多窗口設計：因單詞長度固定，不同起始偏移（
0 ~ wordLen-1）的子串需獨立處理。例如wordLen=3時，起始偏移0、1、2對應子串起始為0、1、2，需分別用窗口覆蓋。 - 窗口詞頻更新：滑動時，通過“移除左側舊單詞、加入右側新單詞”的方式，避免重復截取子串（優化時間復雜度 ）。利用哈希表的增刪操作，高效維護窗口內的詞頻。
- 匹配判斷：每次窗口更新后，直接對比
windows[winIndex]與wordMap，利用哈希表的equals方法快速判斷是否匹配。
三、復雜度分析
（一）時間復雜度
- 初始化多窗口：共
wordLen個窗口，每個窗口截取wordCount個單詞（每個單詞截取時間為O(wordLen)），總時間復雜度為O(wordLen * wordCount * wordLen) = O(wordLen2 * wordCount)。 - 滑動窗口處理：共
sLen - wordCount * wordLen次滑動（近似O(sLen)），每次滑動涉及哈希表的增刪查操作（均為O(1)，單詞數量固定 ），總時間復雜度為O(sLen)。 - 整體時間復雜度：
O(wordLen2 * wordCount + sLen)。因wordLen和wordCount通常遠小于sLen，可近似認為是O(sLen)，滿足題目高效要求。
（二）空間復雜度
- 哈希表存儲：
wordMap存儲wordCount個單詞的詞頻，windows數組存儲wordLen個窗口的詞頻（每個窗口最多wordCount個單詞 ），空間復雜度為O(wordCount + wordLen * wordCount) = O(wordLen * wordCount)。 - 額外空間：結果列表
res存儲符合條件的起始索引，最多O(sLen / wordLen)個元素。整體空間復雜度為O(wordLen * wordCount + sLen / wordLen)，可接受。
串聯所有單詞的子串問題，通過多滑動窗口 + 哈希表的協同策略，巧妙解決了精確匹配與高效遍歷的難題。多窗口覆蓋不同起始偏移，確保不遺漏可能的子串；哈希表實現詞頻快速統計與對比，優化匹配效率。
詳解)
