讨论/算法和数据结构/76 最小覆盖子串 ————运行没有错误,提交出错,代码贴出来,大侠帮忙看看。/
76 最小覆盖子串 ————运行没有错误,提交出错,代码贴出来,大侠帮忙看看。

image.png

class Solution {
public String minWindow(String s, String t) {

    Map<Character,Integer> targetMap = new HashMap<Character,Integer>();
    Map<Character,Integer> windowMap = new HashMap<Character,Integer>();
    
    char[] targetArr = t.toCharArray();
    char[] sourceArr = s.toCharArray();

    int minlength = sourceArr.length;
    int l=0,start = 0,match = 0;
    String res = "";

    for(char c:targetArr){
        if(targetMap.containsKey(c)){
            targetMap.put(c,targetMap.get(c)+1);
        }else{
            targetMap.put(c,1);
        }
    }

    for(int r = 0;r < sourceArr.length;r++){
        char c = sourceArr[r];
        if(windowMap.containsKey(c)){
            windowMap.put(c,windowMap.get(c)+1);
        }else{
            windowMap.put(c,1);
        }
        if(windowMap.get(c) == targetMap.get(c)){
            match++;
        }
        while(match == targetMap.size()){
            if(r-l+1<=minlength){
                start = l;
                minlength = r-l+1;

                res = s.substring(start,start+minlength);
            }
            char tt = sourceArr[l];
            if(targetMap.containsKey(tt)){
                windowMap.put(tt,windowMap.get(tt)-1);
                if(windowMap.get(tt) < targetMap.get(tt)){
                    match--;
                }
            }
            l++;
        }
    }
    return res;


}

}

哪位大侠能帮忙看看。

展开讨论

肉眼看了一下,发现了个bug

if(windowMap.get(c) == targetMap.get(c))

这个是有问题的,Integer不能用==来比较是否相等,应该用equals

你可以用这段代码测试一下

Integer x = 1;
Integer y = 1;
x == y   //这个是true

Integer x = 200;
Integer y = 200;
x == y   //这个是false

为啥呢,因为java内部会对-128到127的Integer进行缓存,所以这范围内的Integer内存地址都相等
其他数,虽然值相等,但内存地址不相等

2