昨天晚上十一点多吧,我在公司楼下抽了口烟,手机一直响,群里小李说“哥,线上日志又炸了,我想把那段最小的请求片段截出来,得包含那几个关键字,不然 Kibana 一搜一屏幕,看吐了”…我一听就乐了,这不就是那个“最小覆盖子串”么,你们平时刷题觉得离业务远,其实真不远,日志、埋点、链路追踪,都是“我就想要最短那一段,但必须把 A/B/C 都带上”。
我当时脑子里第一反应还是老套路:双指针+滑动窗口。就是那个…怎么说呢,像你在外卖袋子里找“筷子+酱包+餐巾纸”,你把袋子口越开越大先确保都找到了,然后再一点点往回收,看看能不能把多余的东西抖出去,最后剩下的那坨就是“最小覆盖”。
关键点就俩: 一个叫 need(目标里每个字符要多少个),一个叫 window(当前窗口里有多少个),再配个 valid(当前有多少种字符满足了 need)。valid 到达“目标种类数”的时候,说明窗口覆盖了,然后就开始收缩 left。
我直接把代码甩群里了,Java 写着也顺手,别嫌我变量名土,我写代码就这样,能跑就行…啊不是,能读就行:
import java.util.*;publicclassMinWindowSubstring{publicstatic 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 = newint[128];int[] window = newint[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); }// 随手测一下publicstaticvoidmain(String[] args){ System.out.println(minWindow("ADOBECODEBANC", "ABC")); // BANC System.out.println(minWindow("a", "aa")); // "" System.out.println(minWindow("aa", "aa")); // "aa" }}
你看这个东西,真正“容易写错”的地方其实不是思路,是细节: 比如 right 我这里是先取字符再 right++,窗口是 [left, right) 这种半开区间,收缩的时候 left++ 也要配套,不然你一会儿 substring 就差一位,线上排查你能被自己气死。还有 valid 的加减,必须卡在“刚好等于 need 的那一刻”才动,不然你会在重复字符上翻车,特别是 t 里有重复字符的时候,很多人写着写着就把 valid 当成“字符数量”了,结果直接错。
对了,小李后来拿这个去做日志定位还挺好用:把那串 traceId 周边的 payload 当成 s,把必须出现的关键字段当成 t,最短一段直接截出来扔工单里,PM 看得懂,研发也省事。你说算法题没用吧…哎算了我不跟你杠了,我这会儿又被喊去看一个超时告警,先这样,回头群里再聊。