76. Minimum Window Substring 发表于 2021-12-05 123456789101112131415161718192021222324252627282930313233343536373839404142class Solution { public String minWindow(String s, String t) { int MAX = 100001; // 注意该值需要大于测试用例字符串最大长度 int startIndex = 0, endIndex = MAX; int[] targetMap = new int[256]; int targetChars = 0; for (int i = 0; i < t.length(); i++) { char c = t.charAt(i); if (targetMap[c]++ == 0) { targetChars++; } } int[] windowMap = new int[256]; int matchChars = 0; int i = 0; for (int j = 0; j < s.length(); j++) { // window: [i, j] char c = s.charAt(j); if (++windowMap[c] == targetMap[c]) { matchChars++; } while (matchChars >= targetChars) { // 注意需要在满足条件时收集 if (j - i < endIndex - startIndex) { startIndex = i; endIndex = j; } char leftmost = s.charAt(i); if (windowMap[leftmost]-- == targetMap[leftmost]) { matchChars--; } i++; } } return endIndex == MAX ? "" : s.substring(startIndex, endIndex + 1); }} Reference76. Minimum Window Substring剑指 Offer II 017. 含有所有字符的最短字符串