leetcode76

Question

package leetcode;

import sun.awt.WindowIDProvider;

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 */
public class LeetCode76 {
    public static String minWindow(String s, String t) {
        if (t.length()>s.length()){
            return "";
        }
        int l = 0,r=-1;
        int min  = s.length()+1;
        String result = "";
        int[] freqs = new int[60];
        int[] save = new int[2];
        for (int i = 0;i<t.length();i++){
            freqs[t.charAt(i)-'A']++;
        }

        while (l<s.length()&&r<s.length()){
            if (r-l+1<t.length()&&r+1<t.length()){
                r++;
            }else {
                if (matching(s.substring(l,r+1),freqs)){
                    if (r-l+1<min){
                        min = r-l+1;
                        save[0]=l;
                        save[1]=r;
                    }
                    l++;
                }else if (r+1<=s.length()){
                    r++;
                }
            }
        }
        if (min<s.length()+1){
            return s.substring(save[0],save[1]+1);
        }else {
            return "";
        }
    }
	//判断匹配的方法
    public static boolean matching(String windowC,int[] freqs){
        int[] windowChar = new int[60];
        for (int j = 0;j<windowC.length();j++){
            windowChar[windowC.charAt(j)-'A']++;
        }

        //进行匹配
        for (int n = 0;n<60;n++){
            if (freqs[n]!=0&&(freqs[n]>windowChar[n])){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        String n = minWindow(s,t);
        System.out.println(n);

    }
}

老师您帮忙看一下需要怎么优化，leetcode前265个测试用例都过了，就最后一个超时了

Answer 1

liuyubobobo 2021-06-29 23:33:37

每次在 matching 中每次都 new 空间并且重新统计当前窗口的字符频率太耗时了。

可以在滑动窗口的过程中，用一个固定数组跟踪当前窗口各个字符的频率。matching 的时候两个数组做比较就好了，不需要每次重新统计，更不需要每次重新开空间。下面是我根据你的代码做的修改，可以 ac，注意 windowFreqs 的使用。

public class Solution {
    public static String minWindow(String s, String t) {
        if (t.length()>s.length()){
            return "";
        }
        int l = 0,r=-1;
        int min  = s.length()+1;
        String result = "";
        int[] freqs = new int[60];
        int[] save = new int[2];
        for (int i = 0;i<t.length();i++){
            freqs[t.charAt(i)-'A']++;
        }
        
        // 注意这里！！！！！！！！！！！
        int[] windowFreqs = new int[60]; 
        while (l<s.length()&&r<s.length()){
            if (r-l+1<t.length()&&r+1<t.length()){
                r++;
                windowFreqs[s.charAt(r) - 'A'] ++; // 维护
            }else {
                // matching 只要两个数组比较就好
                if (matching(windowFreqs,freqs)){
                    if (r-l+1<min){
                        min = r-l+1;
                        save[0]=l;
                        save[1]=r;
                    }
                    windowFreqs[s.charAt(l) - 'A'] --; // 维护
                    l++;
                }else if (r+1<=s.length()){
                    r++;
                    if(r < s.length())
                        windowFreqs[s.charAt(r) - 'A'] ++; // 维护
                }
            }
        }
        if (min<s.length()+1){
            return s.substring(save[0],save[1]+1);
        }else {
            return "";
        }
    }
    
    //判断匹配的方法
    // 注意：matching 中不需要重新开空间，不需要重新统计频率！！！！
    public static boolean matching(int[] windowChar,int[] freqs){
        //进行匹配
        for (int n = 0;n<60;n++){
            if (freqs[n]!=0&&(freqs[n]>windowChar[n])){
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        String n = minWindow(s,t);
        System.out.println(n);
    }
}

• 提问者 不考过程序员不改名字 #1

  老师如果这样做的话，在while循环里的 l++ 之前，已经把 l 位置之前的字母放进了判断频率的数组里，不会对后面的频率判断产生影响嘛

• 提问者 不考过程序员不改名字 #2

  我明白了老师，您在，每次l++之前都已经把 l 对应的频率-1了，这样就不会造成影响了，谢谢您

• liuyubobobo 回复 提问者 不考过程序员不改名字 #3

  对的。继续加油！：）