本文共 2249 字，大约阅读时间需要 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/