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

#76最小覆盖子串

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

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

解题主线

need 记录目标频次，window 只记录目标字符在当前半开区间 [left, right) 中的频次。

formed 统计已达到目标频次的字符种类数；只有 formed == need.size() 时窗口才完整覆盖 t。

右端扩张直到可行，再持续移动左端收缩并更新最短答案，是最小覆盖类滑窗的标准节奏。

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

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

时间复杂度

O(|s| + |t|)，每个 s 中字符至多被左右指针各处理一次

空间复杂度

O(Σ)，Σ 为 t 中不同字符数

76. 最小覆盖子串 · 哈希计数滑动窗口

java

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

final class Solution {
    public String minWindow(String s, String t) {
        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);
                if (count == required) formed++;
            }

            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