LeetCode 76. Minimum Window Substring [Hard]

发表于 | 更新于 | 分类于 ， | 阅读次数：

题目来源：https://leetcode.com/problems/minimum-window-substring/

题目难度：Hard

解答1[Java]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public String minWindow(String s, String t) {
        int[] map = new int[128];
        for (char c : t.toCharArray()) map[c]++;
        int counter = t.length(), left = 0, right = 0, head = 0, d = Integer.MAX_VALUE;
        while (right < s.length()) {
            if (map[s.charAt(right++)]-- > 0) counter--;
            while (counter == 0) {
                if (right - left < d) d = right - (head = left);
                if (map[s.charAt(left++)]++ == 0) counter++;
            }
        }
        return d == Integer.MAX_VALUE ? "" : s.substring(head, head + d);
    }
}

思路

注意 if (map[s.charAt(right++)]-- > 0) 这句，不论 right 指向位置的字符是哪个，在判断之后都会被减去 1。因为在前边的语句中，已经预先把 t 中的字符在 map 中加 1 了，所以只有不在 t 中的字符才会被减成负数。

同理，if (map[s.charAt(left++)]++ == 0) counter++; 如果判断为真，说明 left 指针指向的字符是 t 中的一个字符，且减去这个字符之后，这个字符的数量就不够了，因此需要把 counter 加1。如果 left 指向的不是 t 中的字符，那么这个字符在 map 中的值一定是负数，因为之前 right 遍历的时候被减过。

假设 t="ABC"，当 counter 为零的时候，map['A']、map['B'] 和 map['C'] 其中至少有两个的值是小于等于零的。可以小于零，但至少要等于零。不然 counter 是不会为零的。

当 map['A'] 被减为零之后，如果再遇到字符 A，就不会再减 counter 了。因为 map['A'] 已经被减到零，说明前面已经匹配到的字符 A 的数量已经足够了。