力扣第76题-最小覆盖子串

题目
题目链接

题解

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

class Solution {

    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) {
            return "";
        }
        if (s.length() < t.length() ) {
            return "";
        }
        // 构建哈希表
        // 哈希表k用于存储t中的字符，v存储字符出现的次数
        Map<Character, Integer> table = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            Integer count = table.get(t.charAt(i));
            if (count == null) {
                count = 1;
            } else {
                count++;
            }
            table.put(t.charAt(i), count);
        }

        // p0是左指针（左窗口）p1是右指针（右窗口）
        int p0 = 0, p1 = 0;
        // 状态，当等于0时答案成立，但不一定是最佳答案
        int state = t.length();
        // min最佳答案长度，resP0, resP1最佳答案指针
        int min = Integer.MAX_VALUE, resP0 = -1, resP1 = -1;
        // 滑动窗口遍历
        // p1从头滑到尾
        while (p1 < s.length()) {
            // c代表当前字符应该在s子串上出现的次数，当c等于0时代表当前字符在子串上的数量刚好满足，小于0代表超出要求的数量
            Integer c = table.get(s.charAt(p1));
            // 当前字符不覆盖
            if (c == null) {
                if (p0 == p1) {
                    p0++;
                }
                p1++;
                continue;
            }
            // 当前字符覆盖
            if (c > 0 && state > 0) {
                --state;
            }
            table.put(s.charAt(p1), c - 1);
            // 前指针向后滑动
            while (p0 < p1) {
                // c0和c是一样的意义，只不过是左窗口的那个值的次数
                Integer c0 = table.get(s.charAt(p0));
                // 不存在，左窗口向右滑动
                if (c0 == null) {
                    p0++;
                    continue;
                }
                // 超出次数，左窗口向右滑动
                if (c0 < 0) {
                    table.put(s.charAt(p0), ++c0);
                    p0++;
                    continue;
                }
                // 未超出次数或者不够，结束左窗口滑动跳出循环
                if (c0 >= 0) {
                    break;
                }
            }
            // 记录最佳答案
            if (state == 0) {
                if (min > p1 - p0 + 1) {
                    min = p1 - p0 + 1;
                    resP1 = p1;
                    resP0 = p0;
                }
            }
            p1++;
        }
        if (state == 0) {
            return s.substring(resP0, resP1 + 1);
        }
        return "";
    }
}