笔试时间：2025年8月3日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：最小覆盖子串

给定字符串 src和target， 找出src中最短的(连续)子串 sub，使得 targe是sub 的子序列。如果 src 中没有窗口可以包含 target 中的所有字符，返回空字符串""。如果有不止一个最短长度的窗口，返回开始位置最靠左的那个。

提示：s1是s2子序列的含义是，字符串s2与s1完全相同，或字符串s2去掉部分字符后可以与s1完全相同。注：1.所有输入的字符串都只能包含小写字母。

src 长度的范围为[1,20000]。3.target 长度的范围为|1,100]。其他： 时间限制：3000ms 内存限制：256.0MB

样例输入

s = "ADOBECODEBANC", t = "ABC"

样例输出

"BANC"

解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

参考题解

我们先使用一个哈希表（如 Counter）来统计字符串 t 中每个字符需要出现多少次。这个表我们称为 cnt_t。

它就像是我们的“目标清单”，表示：一个有效子串必须至少包含这些字符和数量。

我们定义两个指针 l 和 r 来表示当前窗口的左右边界（l 是左边界，r 是右边界），窗口的内容就是 s[l:r+1]。

同时，我们使用另一个哈希表 cnt_w 来记录当前窗口中每个字符的数量，方便判断当前窗口是否满足 cnt_t 的要求。

我们从左到右遍历字符串 s，每次将 s[r] 加入窗口并更新 cnt_w。

这样做是为了逐步构建一个可能满足要求的窗口。

每当我们发现当前窗口 cnt_w 已经满足了 cnt_t 的所有要求，就尝试不断移动左指针 l，看看能不能进一步缩小窗口，从而找到更短的答案。

每次成功缩小窗口并且满足条件时，就更新当前最小子串的结果。

为了判断一个窗口是否满足要求，我们写了一个 check() 函数：

• 遍历 cnt_t 中的所有字符；
• 如果当前窗口中某个字符的数量少于要求，就返回 False；
• 否则说明这个窗口是有效的。

在遍历完字符串之后，返回我们记录下的最小有效子串 res，即为最终答案。

C++：

#include <iostream>
#include <unordered_map>
#include <string>
#include <climits>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> cnt_t, cnt_w;
        
        // 初始化目标字符计数
        for (char c : t) {
            cnt_t[c]++;
        }
        
        int left = 0;
        string result = "";
        int min_len = INT_MAX;
        int required = cnt_t.size();
        int formed = 0;
        
        for (int right = 0; right < s.size(); right++) {
            char c = s[right];
            cnt_w[c]++;
            
            // 如果当前字符是目标字符且计数已满足，增加formed
            if (cnt_t.find(c) != cnt_t.end() && cnt_w[c] == cnt_t[c]) {
                formed++;
            }
            
            // 当窗口包含所有目标字符时，尝试收缩左边界
            while (left <= right && formed == required) {
                char left_char = s[left];
                
                // 更新最小窗口
                int current_len = right - left + 1;
                if (current_len < min_len) {
                    min_len = current_len;
                    result = s.substr(left, current_len);
                }
                
                // 移动左边界，更新计数
                if (cnt_t.find(left_char) != cnt_t.end()) {
                    if (cnt_w[left_char] == cnt_t[left_char]) {
                        formed--;
                    }
                    cnt_w[left_char]--;
                }
                
                left++;
            }
        }
        
        return result;
    }
};

int main() {
    Solution solution;
    string s = "ADOBECODEBANC";
    string t = "ABC";
    cout << solution.minWindow(s, t) << endl; // 输出 "BANC"
    return 0;
}
    

Java：

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> cntT = new HashMap<>();
        Map<Character, Integer> cntW = new HashMap<>();
        
        // 初始化目标字符计数
        for (char c : t.toCharArray()) {
            cntT.put(c, cntT.getOrDefault(c, 0) + 1);
        }
        
        int left = 0;
        String result = "";
        int minLen = Integer.MAX_VALUE;
        int required = cntT.size();
        int formed = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            cntW.put(c, cntW.getOrDefault(c, 0) + 1);
            
            // 如果当前字符是目标字符且计数已满足，增加formed
            if (cntT.containsKey(c) && cntW.get(c).intValue() == cntT.get(c).intValue()) {
                formed++;
            }
            
            // 当窗口包含所有目标字符时，尝试收缩左边界
            while (left <= right && formed == required) {
                char leftChar = s.charAt(left);
                
                // 更新最小窗口
                int currentLen = right - left + 1;
                if (currentLen < minLen) {
                    minLen = currentLen;
                    result = s.substring(left, right + 1);
                }
                
                // 移动左边界，更新计数
                if (cntT.containsKey(leftChar)) {
                    if (cntW.get(leftChar).intValue() == cntT.get(leftChar).intVal