剑指offer 专项突破版 17、含有所有字符的最短字符串

题目链接

哈希表+双指针

首先用一个哈希表记录t中所有的字符，出现后对应位置数量–(可以用数组模拟，如果说是字母需要开的大小是58，如果说是小写字母or大写字母，要开的大小是26)然后双指针遍历s，需要注意三点

一个数组即可

判断现在是否包含s应该判断int数组是否每一位都>=0

在移动了left后要进行标记，方便后续更新子数组间距

while (isContains(charNums)) {
    charNums[s.charAt(left++) - 'A']--;
    flag = true;
}
if (flag) {
    if (right - left < end - begin) {
        begin = left - 1;
        end = right;
    }

PS:也可以把更新放到while循环中

class Solution {

    boolean isContains(int[] nums) {
        for (int num : nums) {
            if (0 > num)
                return false;
        }
        return true;
    }

    public String minWindow(String s, String t) {
        int[] charNums = new int[60];
        int begin = 0, end = Integer.MAX_VALUE, left = 0, right = t.length();
        boolean flag = false;

        if(t.length() > s.length())
            return "";

        for (int i = 0; i < t.length(); i++) {
            charNums[t.charAt(i) - 'A']--;
            charNums[s.charAt(i) - 'A']++;
        }
        if (isContains(charNums))
            end = t.length();

        while (right < s.length()) {
            charNums[s.charAt(right++) - 'A']++;
            while (isContains(charNums)) {
                charNums[s.charAt(left++) - 'A']--;
                flag = true;
            }
            if (flag) {
                if (right - left < end - begin) {
                    begin = left - 1;
                    end = right;
                }
                flag = false;
            }
        }
        return end == Integer.MAX_VALUE ? "" : s.substring(begin, end);
    }
}

直接使用哈希表，同样是对于t中出现的字符，直接记录到表中(出现一次，次数-1)为了避免每一次在判断是否是子字符串时都要遍历哈希表的全部，我们维护了一个count变量，注意代码中对count变量的操作(这个方法中我们把更新left和更新子字符串的长度放到了一起)

class Solution {

    public String minWindow(String s, String t) {
        int left = 0, right = 0, minLeft = 0, minRight = Integer.MAX_VALUE, count = 0;
        HashMap charToCount = new HashMap<>();

        if (minRight < right)
            return "";

        for (Character ch : t.toCharArray()) {
            int time = charToCount.getOrDefault(ch, 0);
            if (0 == time)
                count++;
            charToCount.put(ch, time - 1);
        }

        while (right < s.length() &&  left <= right || 0 == count) {
            //此时并未包含所有 t 中的字符
            if (0 != count) {
                char ch = s.charAt(right++);
                //如果字符 ch 是t中的某一个字符
                if (charToCount.containsKey(ch)) {
                    int time = charToCount.get(ch) + 1;
                    charToCount.put(ch, time);
                    if (0 == time)
                        count--;
                }
            } else {
                if (right - left < minRight - minLeft) {
                    minRight = right;
                    minLeft = left;
                }
                char ch = s.charAt(left++);
                if (charToCount.containsKey(ch)) {
                    int time = charToCount.get(ch) - 1;
                    charToCount.put(ch, time);
                    if (-1 == time)
                        count++;
                }
            }
        }
        return minRight == Integer.MAX_VALUE ? "" : s.substring(minLeft, minRight);
    }
}