串联所有单词的子串

所有单词等长,这是题眼:窗口长度恒定,切片位置也固定。难点只剩怎么快速判断窗口内的词集合 == words 集合——交给哈希表数个数。

先用最好懂的写法:逐个起点检查。后面会看到窗口怎么一格格滑、哈希怎么一格格变,这就是动画主体。

先建「需求表」need：把 words 数成需求表 need = {ab:1, cd:1}。之后每个窗口都拿自己的词频去和这张表比——这是判断成功的唯一标准。

把 s 摊成字符 · 准备开窗：把 s="abcdab" 摊成 6 个字符格。紫框是当前窗口,固定占 4 格。起点最大只能到 2,否则窗口会越界。

起点 0 · 窗口就位：第一个窗口停在 [0,3]=「abcd」。开切前词频表全是 0,接下来每隔 2 个字符切一刀,把切到的词记进表里。

起点 0 · 切第 1 个词：起点 0,窗口是「abcd」。先切前两格 ab,它在 need 里,计数表 ab 记 1。还没超 need 的 1,继续切下一个词。

起点 0 · 切第 2 个词：再切后两格 cd,也在 need 里,计数 cd 记 1。窗口切完了,看看词频表和 need 对不对得上。

起点 0 · 比对成功 ✓：本窗口词频 {ab:1, cd:1} 和 need 一模一样!起点 0 命中,记进答案。窗口整段变绿庆祝一下,然后起点右移一格。

起点 1 · 窗口右移一格：起点挪到 1,窗口滑到「bcda」。左边格子 0 滑出窗口(变灰)。词频表清零,重新切词核对。

起点 1 · 切第 1 个词 → 失败：切第一个词就是 bc,need 里压根没这个词!不用再切了,起点 1 当场淘汰,直接跳到下一个起点。

起点 2 · 窗口再右移：起点挪到 2,窗口滑到「cdab」。格子 0、1 都滑出窗口了。词频表再清空,继续切词。

起点 2 · 窗口就位：窗口稳稳停在 [2,5]。开切前先把词频表清零——每个起点都是独立一局,不能用上一窗口的旧计数。

起点 2 · 切第 1 个词：切前两格 cd,在 need 里,计数 cd 记 1,没超需求。这次词序和起点 0 不同(cd 在前),但题目允许任意排列。

起点 2 · 切第 2 个词：再切后两格 ab,也在 need 里,ab 记 1。两个词都切完了,看词频表。

起点 2 · 比对成功 ✓：词频 {ab:1, cd:1} 又和 need 完全一致!起点 2 命中。顺序无所谓,只要每个词的个数对上就行——哈希计数天然不在乎顺序。

所有起点扫完 · 收工：起点只能到 2,全扫完了。命中的是 0 和 2 两处,答案就是 [0, 2]。整个过程 = 窗口固定长度滑动 + 每窗哈希计数核对。

再走一个例子 s="abab", words=["ab","ab"]。这次 need 需要两个 ab,看哈希计数怎么数到 2 才算数。

新例 · 摊开 "abab"：s="abab" 只有 4 格,窗口也是 4 格,所以只有起点 0 一个窗口。need 这次是 {ab:2}。

新例 · 窗口就位：窗口盖住整个 "abab"。词频表清零,need 这次要 ab×2,看能不能切出两个 ab。

起点 0 · 切第 1 个 ab：切前两格 ab,计数 ab=1。注意:这时若只判「ab 在不在」就会以为够了,但 need 要两个,还得继续。

起点 0 · 切第 2 个 ab：再切后两格,又是 ab,计数累加到 2。正好等于 need 的 2,没超额。两个词切完,比对。

新例 · 比对成功 ✓：词频 {ab:2} 和 need 完全相等,起点 0 命中,答案 [0]。正是「数到 2 才算数」——这就是为什么必须比个数而不是比存在。

哈希计数把「集合相等」这件难事变简单:数着数着,只要某个词超了 need 的额度或遇到陌生词,这个起点就废了,提前剪枝省时间。

雷区实演 · 只看「在不在」会错：假设 words=["ab","ab"](need ab:2)。若只看「ab 出现过没」,会把只含 1 个 ab 的窗口错判成功。必须比个数:1 ≠ 2,淘汰。这就是要用计数表的原因。

边界三连：先想最短 s(空答案)、重复词(比个数)、标准多解三种,代码就稳了。

面试追问：把「定长窗口 + 计数相等 + 剪枝优化」讲清楚,是这题面试的得分点。