最小覆盖子串 Java 实现：滑动窗口算法详解与业务场景剖析

最近看到一个挺有意思的分享：有位朋友跳槽去了某大厂，薪资从18k涨到了32k，开心了一个月就开始诉苦了。每天早会、站会、周会、复盘会连轴转，真正能静下心来写代码的时间不足4小时，PPT倒是越做越熟练。更尴尬的是，当他动了想回原公司的念头时，发现人家已经招到新人，没他的位置了。

网友的评论也很有意思，有人说“钱给够了就忍忍”，也有人调侃“把大厂想象得太纯粹”。在我看来，这件事的核心不在于大厂本身“坑不坑”，而在于很多人在跳槽时只看到了薪资数字的跃升，却忽略了随之而来的“隐形成本”——时间被无限切割、产出需要精心包装、工作节奏完全被流程所驱动。大厂就像一套高效但复杂的地铁换乘系统，它能让你更快到达目的地（职业发展），票价也更贵（薪资），但同时也意味着更拥挤的人流、更多的规则，以及每一站都需要“刷卡”（流程审批）。所以在做面试求职相关的决策前，务必了解清楚真实的工作形态，而不仅仅是盯着涨薪幅度。路如果走错了也别太焦虑，复盘清楚，下一次选择时才能更稳健。

从线上问题到算法实战：最小覆盖子串

昨天晚上十一点多，我在公司楼下抽烟，手机一直响。同事小李在群里说：“哥，线上日志又炸了，我想把那段包含特定关键字的、最短的请求片段截取出来，不然Kibana里一搜就是一整屏，看得眼睛疼……”我一听就乐了，这不就是经典的“最小覆盖子串”（Minimum Window Substring）问题吗？很多人觉得刷题离实际业务很远，其实不然。无论是日志过滤、埋点分析还是链路追踪，都会遇到类似需求：“我只要最短的那一段数据，但它必须包含A、B、C这几个关键元素。”

我脑子里第一时间闪过的还是那个经典解法：双指针配合滑动窗口。这就像你在一袋外卖里找齐“筷子、酱包、餐巾纸”三样东西。你的策略是先把袋子口越撑越大（右指针移动），确保三样东西都出现在视野里；一旦找齐，就开始一点点收紧袋口（左指针移动），试着把多余的东西（非目标字符）抖出去，最后剩下的那一小撮，就是你要的“最小覆盖”。

这个算法的关键通常在于维护三个核心变量：

1. need：记录目标字符串t中每个字符需要的数量。
2. window：记录当前滑动窗口内各字符的数量。
3. valid：记录当前窗口内，有多少种字符的数量已经满足了need的要求。当valid等于目标字符串中独特字符的种类数时，说明当前窗口已经覆盖了目标。

我当时直接把代码贴到了群里。用Java写起来很顺手，变量名可能比较接地气，但胜在清晰易懂：

import java.util.*;

public class MinWindowSubstring {
    public static String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length() || t.length() == 0) return "";

        // 如果字符集很大（比如全Unicode），可以把数组换成 HashMap<Character, Integer>
        int[] need = new int[128];
        int[] window = new int[128];

        int kinds = 0; // t里有多少种“需要的字符”
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (need[c] == 0) kinds++;
            need[c]++;
        }

        int left = 0, right = 0;
        int valid = 0;

        int bestLen = Integer.MAX_VALUE;
        int bestL = 0;

        while (right < s.length()) {
            char rc = s.charAt(right);
            right++;

            if (rc < 128 && need[rc] > 0) {
                window[rc]++;
                if (window[rc] == need[rc]) valid++;
            }

            // 覆盖了就收缩
            while (valid == kinds) {
                if (right - left < bestLen) {
                    bestLen = right - left;
                    bestL = left;
                }

                char lc = s.charAt(left);
                left++;

                if (lc < 128 && need[lc] > 0) {
                    if (window[lc] == need[lc]) valid--;
                    window[lc]--;
                }
            }
        }

        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
    }

    // 随手测一下
    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC")); // BANC
        System.out.println(minWindow("a", "aa"));              // ""
        System.out.println(minWindow("aa", "aa"));             // "aa"
    }
}

真正容易出错的地方往往不是算法思路，而是实现细节。比如我这里的写法，right是先取字符再递增，窗口是左闭右开的区间[left, right)。收缩时left++的操作必须与之配套，否则最后用substring截取时就会差一位，线上排查这种Bug能把自己气死。还有valid的增减，必须严格卡在窗口内某个字符的数量“刚好等于”need中要求数量的那一刻，早一点晚一点都会出问题。尤其是当t中包含重复字符时，很多人容易把valid当成“字符总数”来管理，结果导致逻辑错误。

后来小李用这个思路去处理日志定位，效果挺好。他把一整条traceId关联的负载数据当作字符串s，把必须出现的几个关键字段当作目标t，算法跑完直接就能捞出最短的相关日志片段，扔到工单里。产品经理能看明白，研发同事排查也省事。所以，你说算法题到底有没有用？这个问题见仁见智，但多掌握一种思路，关键时刻就能多一个高效的工具。技术人的成长，既需要在大厂流程中保持产出，也离不开在像云栈社区这样的地方持续沉淀和思考。