LeetCode 30困难滑动窗口 · 定长
串联所有单词的子串 图解题解
这道题到底在问什么
给字符串 s 和一组等长单词 words。找出 s 中所有起点,使得从该起点开始、长度等于全部单词拼接长度的子串,恰好是 words 中每个单词各用一次的任意排列拼接。
- s
- "abcdab"
- words
- ["ab","cd"]
- 输出
- [0, 2]
- 解释
- 起点0="abcd"=ab+cd ✓;起点2="cdab"=cd+ab ✓
最优解：一步一步想明白
- 3所有单词等长,这是题眼:窗口长度恒定,切片位置也固定。难点只剩怎么快速判断窗口内的词集合 == words 集合——交给哈希表数个数。
- 4先用最好懂的写法:逐个起点检查。后面会看到窗口怎么一格格滑、哈希怎么一格格变,这就是动画主体。
- 5数清 words 里每个词要几个把 words 数成需求表 need = {ab:1, cd:1}。之后每个窗口都拿自己的词频去和这张表比——这是判断成功的唯一标准。
- 6窗口长度 = 4,起点从 0 开始把 s="abcdab" 摊成 6 个字符格。紫框是当前窗口,固定占 4 格。起点最大只能到 2,否则窗口会越界。
- 7窗口 [0,3],词频表清零第一个窗口停在 [0,3]=「abcd」。开切前词频表全是 0,接下来每隔 2 个字符切一刀,把切到的词记进表里。
- 8窗口 [0,3],取 s[0:2]="ab"起点 0,窗口是「abcd」。先切前两格 ab,它在 need 里,计数表 ab 记 1。还没超 need 的 1,继续切下一个词。
- 9取 s[2:4]="cd"再切后两格 cd,也在 need 里,计数 cd 记 1。窗口切完了,看看词频表和 need 对不对得上。
- 10词频 {ab:1,cd:1} == need本窗口词频 {ab:1, cd:1} 和 need 一模一样!起点 0 命中,记进答案。窗口整段变绿庆祝一下,然后起点右移一格。
- 11窗口 [1,4] = "bcda"起点挪到 1,窗口滑到「bcda」。左边格子 0 滑出窗口(变灰)。词频表清零,重新切词核对。
- 12取 s[1:3]="bc" 不在 need切第一个词就是 bc,need 里压根没这个词!不用再切了,起点 1 当场淘汰,直接跳到下一个起点。
- 13窗口 [2,5] = "cdab"起点挪到 2,窗口滑到「cdab」。格子 0、1 都滑出窗口了。词频表再清空,继续切词。
- 14窗口 [2,5],准备切词窗口稳稳停在 [2,5]。开切前先把词频表清零——每个起点都是独立一局,不能用上一窗口的旧计数。
- 15取 s[2:4]="cd"切前两格 cd,在 need 里,计数 cd 记 1,没超需求。这次词序和起点 0 不同(cd 在前),但题目允许任意排列。
- 16取 s[4:6]="ab"再切后两格 ab,也在 need 里,ab 记 1。两个词都切完了,看词频表。
- 17词频 {ab:1,cd:1} == need词频 {ab:1, cd:1} 又和 need 完全一致!起点 2 命中。顺序无所谓,只要每个词的个数对上就行——哈希计数天然不在乎顺序。
- 18答案 = [0, 2]起点只能到 2,全扫完了。命中的是 0 和 2 两处,答案就是 [0, 2]。整个过程 = 窗口固定长度滑动 + 每窗哈希计数核对。
- 19再走一个例子 s="abab", words=["ab","ab"]。这次 need 需要两个 ab,看哈希计数怎么数到 2 才算数。
- 20need={ab:2},窗口长度=4s="abab" 只有 4 格,窗口也是 4 格,所以只有起点 0 一个窗口。need 这次是 {ab:2}。
- 21窗口 [0,3],词频表清零窗口盖住整个 "abab"。词频表清零,need 这次要 ab×2,看能不能切出两个 ab。
- 22取 s[0:2]="ab"切前两格 ab,计数 ab=1。注意:这时若只判「ab 在不在」就会以为够了,但 need 要两个,还得继续。
- 23取 s[2:4]="ab"再切后两格,又是 ab,计数累加到 2。正好等于 need 的 2,没超额。两个词切完,比对。
- 24{ab:2} == need{ab:2}词频 {ab:2} 和 need 完全相等,起点 0 命中,答案 [0]。正是「数到 2 才算数」——这就是为什么必须比个数而不是比存在。
- 25哈希计数把「集合相等」这件难事变简单:数着数着,只要某个词超了 need 的额度或遇到陌生词,这个起点就废了,提前剪枝省时间。
- 29words=["ab","ab"] 需要两个 ab假设 words=["ab","ab"](need ab:2)。若只看「ab 出现过没」,会把只含 1 个 ab 的窗口错判成功。必须比个数:1 ≠ 2,淘汰。这就是要用计数表的原因。
⚠️ 容易写错的地方
✗ 错：用 if 只检查词「在不在」need
✓ 对：必须用计数比对「个数相等」
words=["a","a"] 时,光看在不在会把只含一个 a 的窗口误判通过
✗ 错：切片时随意取长度
✓ 对：必须按固定词长 wlen 切
单词等长是题眼,切错长度整窗就乱了
✗ 错：起点枚举到 len(s)
✓ 对：起点上限是 len(s) − total
再往后窗口会越界,Python 切片虽不报错但会漏判/错判
完整代码（Python / C++ / Java）
Python
class Solution:
def findSubstring(self, s, words):
if not s or not words: return []
wlen = len(words[0])
total = wlen * len(words) # 窗口固定长度
need = {}
for w in words:
need[w] = need.get(w, 0) + 1 # 需求表
res = []
for start in range(len(s) - total + 1):
seen = {}
j, ok = start, True
while j < start + total:
w = s[j:j+wlen] # 按词长切片
if w not in need:
ok = False; break # 陌生词,淘汰
seen[w] = seen.get(w, 0) + 1
if seen[w] > need[w]:
ok = False; break # 超额,淘汰
j += wlen
if ok: res.append(start)
return resC++
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if (s.empty() || words.empty()) return res;
int wlen = words[0].size();
int total = wlen * (int)words.size();
unordered_map<string,int> need;
for (auto& w : words) need[w]++; // 需求表
for (int start = 0; start + total <= (int)s.size(); start++) {
unordered_map<string,int> seen;
bool ok = true;
for (int j = start; j < start + total; j += wlen) {
string w = s.substr(j, wlen); // 切片
if (!need.count(w)) { ok = false; break; }
if (++seen[w] > need[w]) { ok = false; break; }
}
if (ok) res.push_back(start);
}
return res;
}
};Java
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
if (s == null || s.length() == 0 || words.length == 0) return res;
int wlen = words[0].length();
int total = wlen * words.length;
Map<String,Integer> need = new HashMap<>();
for (String w : words)
need.put(w, need.getOrDefault(w, 0) + 1); // 需求表
for (int start = 0; start + total <= s.length(); start++) {
Map<String,Integer> seen = new HashMap<>();
boolean ok = true;
for (int j = start; j < start + total; j += wlen) {
String w = s.substring(j, j + wlen); // 切片
if (!need.containsKey(w)) { ok = false; break; }
int c = seen.getOrDefault(w, 0) + 1;
seen.put(w, c);
if (c > need.get(w)) { ok = false; break; }
}
if (ok) res.add(start);
}
return res;
}
}复杂度
时间复杂度
O(n × m)
n=s 长度,m=单词个数。起点约 n 个,每个起点最多切 m 个词、每次切片+哈希为 O(L)(L=词长)。整体约 O(n·m·L) → 常按 O(n·m) 记
空间复杂度
O(m × L)
need 与 seen 两张哈希表,各存至多 m 个长度 L 的单词
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 串联所有单词的子串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如何优化到更快?+
用「滑动窗口」:对每个起点偏移 0~wlen−1 各跑一条窗口,词整体进出、增量更新计数,避免每个起点都从头重切,降到约 O(n·L)。
为什么要比个数而非是否存在?+
words 可能含重复词,只有计数完全相等才说明窗口是它的一个排列;否则 ["a","a"] 这类会误判。
遇到陌生词怎么处理?+
立刻判定当前起点失败、提前 break,这是重要剪枝,能砍掉大量无效窗口。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 串联所有单词的子串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。