快手面试官：“简历上agent实习挺不错的，写个算法吧，最小覆盖子串”，我笑了，面试官：“笑啥？”，我：“这题我没做过。。。”

给你一个字符串s、一个字符串t。返回s中涵盖t所有字符包括重复字符的最小子串。如果s中不存在涵盖t所有字符的子串则返回空字符串。注意对于t中重复字符我们寻找的子串中该字符数量必须不少于t中该字符数量。如果s中存在这样的子串我们保证它是唯一的答案。示例 1输入s “ADOBECODEBANC”, t “ABC”输出“BANC”解释最小覆盖子串 “BANC” 包含来自 t 的 ‘A’、‘B’ 和 ‘C’。示例 2输入s “a”, t “a”输出“a”示例 3输入s “a”, t “aa”输出“”解释t 中两个字符 ‘a’ 均应包含在 s 的子串中因此没有符合条件的子串返回空字符串。提示m s.lengthn t.length1 m, n 10^5s 和 t 由英文字母组成进阶你能设计一个在o(mn)时间内解决此问题的算法吗思路暴力解法这道题最直观的思路是什么暴力枚举 s 的所有子串判断子串是否覆盖了 t 的所有字符含重复在所有满足条件的子串中找最短的。时间复杂度 O(n^2 × m)其中 n 是 s 的长度m 是 t 的长度。这个复杂度显然太高了会超时。滑动窗口这道题是经典的滑动窗口问题和之前做过的 209.长度最小的子数组 思路非常类似只不过那道题是求和满足条件这道题是字符覆盖满足条件。滑动窗口的核心思想就是right 指针不断右移扩大窗口直到窗口内的内容满足了要求覆盖了 t 的所有字符left 指针不断右移缩小窗口直到窗口内的内容不再满足要求在这个过程中记录所有满足条件的最小窗口我们来看一下滑动窗口的原理图如图所示滑动窗口就是不断「扩大 → 缩小 → 扩大 → 缩小」的过程在满足条件的窗口中找最小的那个。关键问题但是这道题的难点在于如何判断窗口是否覆盖了 t 的所有字符t 中可能有重复字符比如 t “AABC”那窗口中必须至少有 2 个 A、1 个 B、1 个 C 才算覆盖。这时候就需要用到哈希表来统计字符的需求数量。我们定义两个哈希表need记录 t 中每个字符需要的数量window记录当前窗口中每个字符的数量另外我们可以用一个变量count来记录当前窗口中已经满足需求的字符种类数不是字符个数。当count need.size()时说明窗口已经覆盖了 t 的所有字符。为什么用已满足的字符种类数而不是已满足的字符个数因为 t 中可能有重复字符比如 t “AAB”need 的大小是 2A 和 B 两种不是 3。我们只需要关心每种字符是否满足需求而不需要关心总共有多少个字符。算法流程结合上面的分析完整的滑动窗口算法流程如下用 need 哈希表统计 t 中每个字符的出现次数初始化 left 0, right 0, count 0right 不断右移如果 s[right] 是 t 中的字符更新 window如果该字符数量刚好满足需求count当 count need.size() 时尝试收缩窗口left 不断右移收缩窗口如果 s[left] 是 t 中的字符更新 window如果该字符数量不够了count–更新最小窗口的起始位置和长度重复 3-4 直到 right 遍历完 s让我们用题目示例 s “ADOBECODEBANC”, t “ABC” 来一步步模拟从图中可以清楚看到整个滑动窗口的移动过程right 从 0 移到 5窗口 [ADOBEC] 第一次满足条件长度 6left 右移缩小窗口移除 A 后不再满足条件right 继续右移到 10窗口 [BECODEBA] 再次满足条件但长度 8 大于之前的 6left 右移缩小窗口移除 B、E、C 后不再满足right 继续右移到 12窗口包含 ABCleft 右移缩小后得到 [BANC]长度 4最终结果为 “BANC”代码实现有了上面的分析代码就不难写了。C代码如下class Solution {public: string minWindow(string s, string t) { unordered_mapchar, int need, window; for (char c : t) need[c]; int left 0, right 0; int count 0; // 记录窗口中满足need要求的字符种类数 int start 0, minLen INT_MAX; // 记录最小窗口的起始位置和长度 while (right s.size()) { char c s[right]; right; // 如果是t中的字符更新window if (need.count(c)) { window[c]; // 字符c的数量刚好满足需求count if (window[c] need[c]) { count; } } // 当窗口满足条件时尝试收缩 while (count need.size()) { // 更新最小窗口 if (right - left minLen) { start left; minLen right - left; } char d s[left]; left; // 如果移除的是t中的字符更新window if (need.count(d)) { // 字符d的数量不再满足需求count-- if (window[d] need[d]) { count--; } window[d]--; } } } return minLen INT_MAX ? : s.substr(start, minLen); }};时间复杂度: O(m n)其中 m 是 s 的长度n 是 t 的长度。left 和 right 指针各自最多遍历 s 一次。空间复杂度: O(k)k 是字符集的大小这里是英文字母最多 52 个。代码详解我们来仔细分析一下代码中的几个关键点1. 什么时候 countif (window[c] need[c]) { count;}只有当字符 c 在窗口中的数量刚好等于需求时count 才增加。如果 window[c] 已经大于 need[c]说明之前已经满足过了不需要重复计数。2. 什么时候 count–if (window[d] need[d]) { count--;}只有当字符 d 在窗口中的数量刚好等于需求时移除它才会导致不满足。如果 window[d] 已经大于 need[d]移除一个仍然满足需求。3. 为什么要先判断再减注意收缩窗口时的判断顺序先判断window[d] need[d]再执行window[d]--。因为如果先减再判断就无法知道减之前是否刚好满足需求了。4. 内层 while 还是 if很多录友们可能会问为什么内层用 while 而不是 if因为一次收缩可能不够。比如 s “AAAABC”, t “ABC”当 right 到达 C 时窗口满足条件但 left 需要跳过前面多余的 A 才能找到最小窗口。用 while 可以持续收缩直到窗口不再满足条件。学AI大模型的正确顺序千万不要搞错了2026年AI风口已来各行各业的AI渗透肉眼可见超多公司要么转型做AI相关产品要么高薪挖AI技术人才机遇直接摆在眼前有往AI方向发展或者本身有后端编程基础的朋友直接冲AI大模型应用开发转岗超合适就算暂时不打算转岗了解大模型、RAG、Prompt、Agent这些热门概念能上手做简单项目也绝对是求职加分王给大家整理了超全最新的AI大模型应用开发学习清单和资料手把手帮你快速入门学习路线:✅大模型基础认知—大模型核心原理、发展历程、主流模型GPT、文心一言等特点解析✅核心技术模块—RAG检索增强生成、Prompt工程实战、Agent智能体开发逻辑✅开发基础能力—Python进阶、API接口调用、大模型开发框架LangChain等实操✅应用场景开发—智能问答系统、企业知识库、AIGC内容生成工具、行业定制化大模型应用✅项目落地流程—需求拆解、技术选型、模型调优、测试上线、运维迭代✅面试求职冲刺—岗位JD解析、简历AI项目包装、高频面试题汇总、模拟面经以上6大模块看似清晰好上手实则每个部分都有扎实的核心内容需要吃透我把大模型的学习全流程已经整理好了抓住AI时代风口轻松解锁职业新可能希望大家都能把握机遇实现薪资/职业跃迁这份完整版的大模型 AI 学习资料已经上传CSDN朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费】