題目描述:給定字串 s 和一個由等長單詞組成的陣列 words,找出 s 中所有是 words 中所有單詞串接的子字串的起始索引。每個單詞必須恰好使用一次,但順序任意。
解題思路:每個單詞長度相同(設為 w),總窗口長度為 words.size() * w。對每個偏移 [0, w) 做滑動窗口:以 w 為步進移動右邊界,遇到合法單詞就加入窗口計數,超限時縮小左邊界,窗口恰好包含所有單詞時記錄起始索引。
時間複雜度:O(n × w) — 共 w 個偏移,每個偏移滑動窗口掃描 O(n) 個字元;每次子字串提取為 O(w)。
空間複雜度:O(m × w) — 雜湊表儲存 words 的頻率與當前窗口計數,最多 m 個條目,每條目長 w。
1. Build frequency map `need` from words (word length = w)
2. For each offset off in [0, w):
a. Init empty window map, left = off, count = 0
b. For right = off to n-w in steps of w:
- word = s[right..right+w)
- If word in need:
* window[word]++, count++
* While window[word] > need[word]: shrink left by w, count--
* If count == m: append left to result
- Else: clear window, count = 0, left = right + w
3. Return result暴力法 O(n × m × w):對每個起點切割成 m 個單詞並與 words 比對 — 正確但在 n 和 m 很大時過慢。
固定窗口哈希比對 O(n × m):對每個起點建立完整窗口哈希表與 need 比對,不使用滑動;功能正確但無法共享相鄰窗口的計算結果。