1
2

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

1
2

输入：s = "a", t = "a"
输出："a"

1
2
3
4

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 滑动窗口 + hashmap(可用固定数组代替)
    /// 1. 窗口右边界滑动时,检查当前字符在窗口内出现的次数是否达到目标字符串;
    /// 2. 如果达到,则增加有效计数;
    /// 3. 检查窗口左边界字符出现次数是否超过目标字符串中字符次数, 如果超过,则右滑左边界;
    /// 4. 检查有效计数是否达到目标字符串大小,如果达到,则更新结果字符串;
    pub fn min_window(s: String, t: String) -> String {
        let mut min_substr = "";

        let mut t_stat = vec![0; 60]; // 目标字符串字符频次统计
        let mut w_stat = vec![0; 60]; // 滑动窗口内字符频次统计

        // 统计目标字符串中各字符次数
        t.bytes().map(|b| (b - b'A') as usize).for_each(|id| {
            t_stat[id] += 1;
        });

        let mut sb = s.as_bytes();
        let mut valid_count = 0; //窗口内有效字符计数
        let mut l = 0; // 滑动窗口左右边界
        for r in 0..sb.len() {
            let ri = (sb[r] - b'A') as usize;
            // 增加滑动窗口内部右边界字符频次统计
            w_stat[ri] += 1;
            // 如果当前字符不在目标字符串内
            if t_stat[ri] == 0 {
                continue;
            }
            // 如果当前字符频次未超过目标字符串内字符频次
            if w_stat[ri] <= t_stat[ri] {
                valid_count += 1; // 有效字符计数递增
            }
            // 处理滑窗左边界
            while l < r {
                let li = (sb[l] - b'A') as usize;
                // 如果窗口左边界字符频次 超过 目标字符频次
                if w_stat[li] > t_stat[li] {
                    l += 1; // 滑动左边界
                    w_stat[li] -= 1; // 滑窗中的字符次数递减
                } else {
                    break;
                }
            }

            // 如果当前窗口内有效字符数 == 目标字符数
            if valid_count == t.len() {
                // 如果
                if min_substr.is_empty() || r - l + 1 < min_substr.len() {
                    min_substr = &s[l..=r];
                }
            }
        }

        min_substr.to_string()
    }
}
// @lc code=end

struct Solution;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    /*
    * ## 解题思路
    * * 滑动窗口
    * * 右指针r: 如果当前窗口没有完整包含t，则r右移，扩大窗口范围，直到窗口完整包含t；
    * * 左指针l: 如果当前已经完整包含t，则l右移，减小窗口范围，直到窗口为完整包含t的最小窗口；
    * *
    */
    string minWindow(string s, string t) {
        string res;   //结果
        unordered_map<char, int> s_map;   //当前窗口内字符数统计
        unordered_map<char, int> t_map;   //目标字符数统计
        int valid_count = 0;      //当前窗口内的有效字符数

        // 初始化目标hash数组
        for(auto c: t) t_map[c]++;
        //
        for(int r=0, l=0; r<s.length(); r++) {
            s_map[s[r]]++;     //当前窗口内字符数+1；
            //当前字符统计数未超过目标字符统计数是，
            if(s_map[s[r]] <= t_map[s[r]]) valid_count++;
            // 当前窗口内左字符有效字符数>目标字符数，滑动左指针
            while(s_map[s[l]] > t_map[s[l]]) s_map[s[l++]]--;
            // 刚好
            if (valid_count == t.length()) {
                if(res.empty() || r+1-l < res.size()) {
                    res=s.substr(l, r+1-l);
                }
            }
        }
       return res;
    }
};