前言

LeetCode 第 30 题「串联所有单词的子串」（Substring with Concatenation of All Words）给定一个字符串s和一个单词数组words，数组中所有单词长度相同。要求找出s中所有这样的起始下标：从该位置开始的子串，恰好由words中的每个单词各拼接一次组成，单词之间不重叠，顺序任意。

这道题的难点不在「怎么判断一组单词是否齐全」，而在「怎么在长字符串里高效地枚举所有等长窗口」。朴素做法对每个起始位置切出若干单词、逐个计数，复杂度与字符串长度、单词数量、单词长度三者相乘；数据量大时会超时。更稳的做法是按单词长度分组滑动窗口，把「枚举起点」变成「按固定步长移动」。

常见误解有三个：把窗口按字符逐个滑动，导致切出来的片段不对齐单词边界；用std::set去重，丢掉重复单词的次数信息；窗口内某个单词超出配额时只减计数不移动左边界，导致窗口长度失控。本文先讲朴素思路，再讲按偏移的滑动窗口，最后给出完整代码与边界处理。

一、问题拆解与朴素思路

所有单词长度相同，记为w；单词个数记为m。那么目标子串的长度固定为m * w。若s的长度小于这个值，直接返回空结果。

朴素做法：对每个起始下标start（从 0 到s.size() - m*w），把长度为m*w的片段按w切成m段，统计每段出现的次数，与words的频率表比较；完全一致就记录start。

这个做法正确，但复杂度是 O(nmw) 级别：外层 n 个起点，内层 m 个单词，每次切单词还要 O(w)。当 n 很大、m 也很大时，重复计算非常多。注意，不能简单用「排序后比较」来优化，因为排序本身也带 log 因子，而且每次窗口都要重排。

关键观察是：目标子串的长度固定，且切分点相对于起点的偏移是0, w, 2w, ...。如果两个起点相差w，它们切出的单词边界是对齐的，窗口只是整体右移了一个单词。于是可以按「起点模 w 的余数」分成 w 组，每组内以 w 为步长滑动，维护窗口内单词的计数。这样每个单词最多被加入和移出窗口一次，避免了重复切分。

二、按偏移滑动窗口

外层循环offset从 0 到w-1，表示这一组窗口的起点对 w 取模的余数。内层用两个指针left、right，都从offset开始，每次移动w：

1. 
   
2. 从right位置切出一个长度为w的单词，right += w。
3. 
   
4. 如果这个单词不在words里，说明当前窗口不可能再延续，清空窗口计数，把left移到right，count归零，继续。
5. 
   
6. 如果单词在words里，加入窗口计数，count加一。
7. 
   
8. 如果窗口内该单词的数量超过了words中的数量，就从left开始不断移除单词，直到不超额；每移除一个，left += w，count减一。
9. 
   
10. 如果count == m，说明窗口恰好包含 m 个单词且每个都不超额，由于总数相等，频率必然完全匹配，记录left。
11. 
    

第 4 步的「不断移除」是重点。超额可能不止一个，例如words = ["a", "a"]，窗口里连续出现三个"a"，需要从左边移除到只剩两个。只移除一次就继续，窗口会一直带着多余的单词，count也会偏大，后续判断全部错位。

第 5 步之所以能直接判定，是因为窗口里的单词总数等于 m，且每个单词的计数都不超过需求；在总数相等的前提下，「每个都不超」等价于「每个都恰好相等」。这比逐个比较频率表更省事，也避免了遍历整个 map。

遇到不在words中的单词时，窗口必须整体作废，不能只把left前移一个单词。因为这个未知单词把窗口切断了：任何跨越它的窗口都不可能由words组成。把left = right放在切出单词之后，正好跳过这个未知单词。

三、边界与正确性细节

单词长度不一致。题目保证所有单词长度相同；如果实际输入不满足，算法前提就不成立，应当直接返回空结果，或在入口处检查并报错。不要用第一个单词的长度去切分，然后假设其他单词也一样长。

空单词。若w == 0，窗口长度恒为 0，left、right永远不前进，会死循环。入口处必须拦截。LeetCode 的约束通常保证单词非空，但函数作为独立实现应有防御。

总长度不足。m * w可能大于s.size()，此时直接返回。计算乘积前先判断m > s.size() / w，可以避免乘法溢出（虽然本题规模下不会溢出，但这是好习惯）。

重复单词。words = ["foo", "foo", "bar"]时，频率表里foo的计数是 2。窗口里出现第三个foo就必须从左边移除，直到foo回到 2 个。用set会丢失次数，用map且只记录「是否出现」同样会错。

结果顺序。外层按 offset 分组，内层从左到右，得到的下标不一定是全局升序。LeetCode 通常不要求顺序，但如果需要，最后std::sort一次即可。不要假设当前顺序就是升序。

结果重复。一个合法的起始下标只属于一个 offset 组（start 对 w 取模唯一），因此不会在不同组里被重复加入。若代码改成对每个起点都跑一遍窗口，就可能重复，需要额外去重。

四、完整实现

// 适用于 C++17
#include <algorithm>
#include <string>
#include <unordered_map>
#include <vector>

std::vector<int> findSubstring(const std::string& s,
const std::vector<std::string>& words) {
std::vector<int> result;
if (s.empty() || words.empty()) {
return result;
}

const std::size_t w = words[0].size();
const std::size_t m = words.size();
if (w == 0 || m > s.size() / w) {
return result;
}

std::unordered_map<std::string, int> need;
for (const std::string& word : words) {
++need[word];
}

for (std::size_t offset = 0; offset < w; ++offset) {
std::unordered_map<std::string, int> window;
std::size_t left = offset;
std::size_t right = offset;
std::size_t count = 0;

while (right + w <= s.size()) {
const std::string word = s.substr(right, w);
right += w;

const auto it = need.find(word);
if (it == need.end()) {
window.clear();
count = 0;
left = right;
continue;
}

++window[word];
++count;

while (window[word] > it->second) {
const std::string leftWord = s.substr(left, w);
--window[leftWord];
--count;
left += w;
}

if (count == m) {
result.push_back(static_cast<int>(left));
}
}
}

std::sort(result.begin(), result.end());
return result;
}

复杂度：外层 w 组，内层总共扫描约 n/w 个单词，合计约 n 个单词位置；每个位置做一次长度为 w 的substr与哈希，时间大致 O(nw)，空间 O(mw)（存放单词键）。如果 w 很大，substr的拷贝会成为瓶颈，可以改用std::string_view作为键（C++17），但需要为string_view提供哈希，且要保证s的生命周期覆盖整个 map；这类优化要在确认瓶颈后再做，不要一开始就把代码写复杂。

std::sort只是为了输出有序，题目不要求时可以去掉。排序不会改变结果的正确性，也不会引入重复。

常见坑点

1. 按字符滑动窗口

❌left++、right++，窗口切出的片段不对齐单词边界。

✅ 外层按offset分组，内层每次移动w。

2. 用 set 记录单词

❌std::unordered_set<std::string> need(words.begin(), words.end());

✅ 用unordered_map记录每个单词的需求次数。

3. 超额时只移除一次

❌if (window[word] > need[word]) { ... left += w; }

✅while (window[word] > need[word])，直到不超额。

4. 遇到未知单词不清空窗口

❌ 只把left前移一个单词，窗口仍带着旧计数。

✅window.clear(); count = 0; left = right;。

5. 忘记判断总长度

❌s.size() < m * w时仍进入循环，切出越界片段。

✅ 入口判断m > s.size() / w直接返回。

6. 空单词导致死循环

❌w == 0时right + w <= s.size()永远成立，right不前进。

✅ 入口拦截w == 0。

7. 认为结果天然有序

❌ 直接返回按 offset 分组收集的数组。

✅ 需要升序就std::sort，或不要对顺序做假设。

8. 单词长度不一致仍按第一个长度切

❌ 默认所有单词等长，不检查输入。

✅ 入口校验所有单词长度一致，不一致直接返回空。

总结

这道题的关键是把「枚举所有起点」转成「按单词边界对齐的滑动窗口」。只要窗口每次移动一个单词、超额时循环收缩、未知单词整段作废，频率比较就可以用「总数 + 不超额」代替逐项比对，代码短且不容易漏掉重复单词的情况。