本文共 2210 字，大约阅读时间需要 7 分钟。

描述

给你一个字符串 s 和一个字符串 t。任务是从 s 中找出一个最短的子串，使得这个子串包含 t 中的所有字符。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。

注意

如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例1：

输入：s = "ADOBECODEBANC"，t = "ABC"。输出："BANC"。

示例2：

输入：s = "a"，t = "a"。输出："a"。

进阶问题

你能设计一个在 O(n) 时间内解决此问题的算法吗？

##思路

使用滑动窗口（Sliding Window）技术来解决这个问题，这种技术允许在 O(n) 时间复杂度内完成任务。滑动窗口通过使用两个哈希表 window 和 needs 来追踪当前窗口内的字符及其出现次数，以及 t 中字符的出现次数。

具体步骤如下：

在实现过程中，需要注意：

• 使用哈希表记录字符出现次数，确保能够快速判断字符是否满足需求。
• 刚进入窗口时避免频繁遍历，减少额外时间复杂度。
• 正确处理窗口扩展和收缩过程中的字符出现变化，确保计数准确。
• 当窗口不满足条件时，及时停止，避免不必要的计算。

通过以上步骤，可以有效找到满足條件的最短子串，或者判断其不存在并返回空字符串。

解答代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;class Solution {public:    string minWindow(string s, string t) {        int minLen = INT_MAX;        unordered_map
      
        window;        unordered_map
       
         needs;        for (char c : t) {            needs[c]++;        }        int l = 0, r = 0, match = 0, res_start = 0;        while (r != s.size()) {            char c_right = s[r];            if (needs.count(c_right)) {                window[c_right]++;                if (window[c_right] == needs[c_right]) {                    match++;                }            }            r++;            while (match == needs.size()) {                if (r - l < minLen) {                    res_start = l;                    minLen = r - l;                }                char c_left = s[l];                if (needs.count(c_left)) {                    window[c_left]--;                    if (window[c_left] < needs[c_left]) {                        match--;                    }                }                l++;            }        }        return (minLen == INT_MAX) ? "" : s.substr(res_start, minLen);    }};
       
      
     
    
   

代码解释

通过这种方法，可以在 O(n) 时间复杂度内解决问题，适用于大规模字符串处理。

转载地址：http://dpusz.baihongyu.com/