Leetcode 76 Minimum Window Subst

原题：Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the empty string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

解题报告

本题求包含t字符串的最小子串，与第209题很相像，同样是定义左右两个指针。先找到一个符合标准的子串，然后分别移动左右指针，得到符合标准的最小子串。

解题思路

1、定义一个hashMap，存储t中的元素和出现的次数，定义count变量。
2、定义count变量，存储t的长度。
右侧指针向后移动当count为零的时候，说明左右指针之间的substring是符合标准的一个子串。
3、移动左指针，直到两个指针之间的substring不完全包含t
4、循环直到找到最小的子串。

代码

class Solution {
    public String minWindow(String s, String t) {
        int start = 0;
        int end = 0;
        char[] sum = s.toCharArray();
        char[] sub = t.toCharArray();
        HashMap<Character, Integer> temp = new HashMap<>();
        String result = s + " ";
        int count = sub.length;
        for (int i = 0; i < sub.length; i++) {
            if (temp.containsKey(sub[i]) ) {
                temp.put(sub[i], temp.get(sub[i]) + 1);
            } else {
                temp.put(sub[i], 1);
            }
        }

        while (end < s.length()) {
            if (temp.containsKey(sum[end]) ) {
                int flag = temp.get(sum[end]);
                if(flag > 0){//防止s与t中字符多对一的情况
                    count--;
                }
                temp.put(sum[end], --flag);//如果s中包含t的某个字符，在temp中减去
            }
            end++;
            //System.out.println("end" + end + "count:" + count + "start:" + start);
            //System.out.println("reuslt:" + result);
            if (count == 0) {
                while (start < end && count == 0) {
                    if (temp.containsKey(sum[start])) {//start 指向的字符是t中的字符
                        int flag = temp.get(sum[start]);
                       // System.out.println("flag:" + flag);
                        if (flag >= 0) {   //如果flag<0说明子串中还有该元素
                            count++;
                            result = result.length() > end - start ? s.substring(start, end) : result;
                            
                        }
                        temp.put(sum[start], flag + 1);
                    }
                    start++;
                }
            }
            //System.out.println("result:" + result);
        }
        return result.length() ==s.length() + 1 ? "" : result;
    }

总结

我认为这道题的难点在于，对s中重复字符的判断。所以，temp中value记录实是s与t中对应key元素的差值。当temp中value大于0，说明s的子串中没有这个key元素；当value小于0，说明s中key元素的个数是多余t的。因此这一点要认识清楚。