双指针与滑动窗口困难1 种解法

#76最小覆盖子串

在 s 中寻找包含 t 全部字符及其重复次数的最短连续子串。

#字符串#哈希表#滑动窗口

原题

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

测试用例保证答案唯一。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

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

提示：

m == s.length
n == t.length
1 <= m, n <= 10⁵
s 和 t 由英文字母组成

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

查看原题

解题主线

need 记录目标频次，window 只记录目标字符在当前半开区间 [left, right) 中的频次。
formed 统计已达到目标频次的字符种类数；只有 formed == need.size() 时窗口才完整覆盖 t。
右端扩张直到可行，再持续移动左端收缩并更新最短答案，是最小覆盖类滑窗的标准节奏。

解法 1：哈希计数滑动窗口

扩张右边界补齐所需字符；窗口覆盖完整后收缩左边界，在失去覆盖能力前记录最短区间。

时间复杂度： O(|s| + |t|)，每个 s 中字符至多被左右指针各处理一次
空间复杂度： O(Σ)，Σ 为 t 中不同字符数

JAVA

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

final class Solution {
    public String minWindow(String s, String t) {
        // 空目标必须提前返回，否则 formed 与 need.size() 会一直相等并导致过度收缩。
        if (s == null || t == null) {
            throw new IllegalArgumentException("strings must not be null");
        }
        if (t.isEmpty() || s.isEmpty() || t.length() > s.length()) return "";

        Map<Character, Integer> need = new HashMap<>();
        for (char character : t.toCharArray()) {
            need.merge(character, 1, Integer::sum);
        }

        Map<Character, Integer> window = new HashMap<>();
        int formed = 0;
        int left = 0;
        int bestStart = 0;
        int bestLength = Integer.MAX_VALUE;

        for (int right = 0; right < s.length(); right++) {
            char added = s.charAt(right);
            Integer required = need.get(added);
            if (required != null) {
                int count = window.merge(added, 1, Integer::sum);
                // formed 只在某类字符的频次首次达到要求时增加。
                if (count == required) formed++;
            }

            // 窗口可行时持续收缩左边界，枚举以当前 right 结尾的最短覆盖窗口。
            while (formed == need.size()) {
                int length = right - left + 1;
                if (length < bestLength) {
                    bestStart = left;
                    bestLength = length;
                }

                char removed = s.charAt(left++);
                required = need.get(removed);
                if (required != null) {
                    int count = window.get(removed);
                    if (count == required) formed--;
                    if (count == 1) window.remove(removed);
                    else window.put(removed, count - 1);
                }
            }
        }
        return bestLength == Integer.MAX_VALUE
            ? ""
            : s.substring(bestStart, bestStart + bestLength);
    }
}

边界与易错点

t 为空时 need.size() 为 0，旧循环会无限收缩并最终越界；整理后立即返回空串。
旧 need/window 是实例字段，多次调用同一个对象会残留频次；整理后改为方法局部状态。
字符重复次数必须精确比较；formed 只在频次首次达到或刚从达标降到不足时变化。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/zhard/Q076_minWindow.java