C++实现LeetCode(30.串联所有单词的子串)

前言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从right位置切出一个长度为w的单词right w。如果这个单词不在words里说明当前窗口不可能再延续清空窗口计数把left移到rightcount归零继续。如果单词在words里加入窗口计数count加一。如果窗口内该单词的数量超过了words中的数量就从left开始不断移除单词直到不超额每移除一个left wcount减一。如果count m说明窗口恰好包含 m 个单词且每个都不超额由于总数相等频率必然完全匹配记录left。第 4 步的「不断移除」是重点。超额可能不止一个例如words [a, a]窗口里连续出现三个a需要从左边移除到只剩两个。只移除一次就继续窗口会一直带着多余的单词count也会偏大后续判断全部错位。第 5 步之所以能直接判定是因为窗口里的单词总数等于 m且每个单词的计数都不超过需求在总数相等的前提下「每个都不超」等价于「每个都恰好相等」。这比逐个比较频率表更省事也避免了遍历整个 map。遇到不在words中的单词时窗口必须整体作废不能只把left前移一个单词。因为这个未知单词把窗口切断了任何跨越它的窗口都不可能由words组成。把left right放在切出单词之后正好跳过这个未知单词。三、边界与正确性细节单词长度不一致。题目保证所有单词长度相同如果实际输入不满足算法前提就不成立应当直接返回空结果或在入口处检查并报错。不要用第一个单词的长度去切分然后假设其他单词也一样长。空单词。若w 0窗口长度恒为 0left、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 取模唯一因此不会在不同组里被重复加入。若代码改成对每个起点都跑一遍窗口就可能重复需要额外去重。四、完整实现// 适用于 C17#include algorithm#include string#include unordered_map#include vectorstd::vectorint findSubstring(const std::string s,const std::vectorstd::string words) {std::vectorint 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_mapstd::string, int need;for (const std::string word : words) {need[word];}for (std::size_t offset 0; offset w; offset) {std::unordered_mapstd::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_castint(left));}}}std::sort(result.begin(), result.end());return result;}复杂度外层 w 组内层总共扫描约 n/w 个单词合计约 n 个单词位置每个位置做一次长度为 w 的substr与哈希时间大致 O(nw)空间 O(mw)存放单词键。如果 w 很大substr的拷贝会成为瓶颈可以改用std::string_view作为键C17但需要为string_view提供哈希且要保证s的生命周期覆盖整个 map这类优化要在确认瓶颈后再做不要一开始就把代码写复杂。std::sort只是为了输出有序题目不要求时可以去掉。排序不会改变结果的正确性也不会引入重复。常见坑点1. 按字符滑动窗口❌left、right窗口切出的片段不对齐单词边界。✅ 外层按offset分组内层每次移动w。2. 用 set 记录单词❌std::unordered_setstd::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. 单词长度不一致仍按第一个长度切❌ 默认所有单词等长不检查输入。✅ 入口校验所有单词长度一致不一致直接返回空。总结要点结论目标长度m * w固定枚举方式按start % w分 w 组组内以 w 步进窗口维护频率表 窗口内单词计数超额处理从左侧循环移除直到不超额未知单词清空窗口left right命中条件count m时间约 O(nw)空间 O(mw)边界空串、空单词、长度不足、重复单词这道题的关键是把「枚举所有起点」转成「按单词边界对齐的滑动窗口」。只要窗口每次移动一个单词、超额时循环收缩、未知单词整段作废频率比较就可以用「总数 不超额」代替逐项比对代码短且不容易漏掉重复单词的情况。