讨论/技术交流/力扣76题一直过不去,球球大佬解答一下/
力扣76题一直过不去,球球大佬解答一下
public static String minWindow(String s, String t) {
        Map<Character,Integer> map = new HashMap<>();
        Map<Character,Integer> need = new HashMap<>();
        int b=1;
        for (char k:t.toCharArray()){
            need.put(k,b);
        }
        int left=0,right=0;
        int start = 0, len = Integer.MAX_VALUE;
        int valid = 0;
        while(right < s.length()){
            char c = s.charAt(right);
            right ++;
            if (need.containsKey(c)){
                map.put(c,map.getOrDefault(c,0)+1);
                if (map.get(c) == need.get(c)){
                    valid++;
                }
            }
            while(valid == need.size()){
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)){
                    if (map.get(d) == need.get(d)){
                        valid--;
                    }
                    map.put(d,map.get(d)-1);
                }
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start,len);
    }
共 2 个回复
public static String minWindow(String s, String t) {
        Map<Character,Integer> map = new HashMap<>();
        Map<Character,Integer> need = new HashMap<>();
        int b=1;
        for (char k:t.toCharArray()){
            need.put(k,b);
            //need中所有字母都只记了1次, 执行need.get(c) == map.get(c)时会出错
            // => need.put(k, need.getOrDefault(k, 0) + 1);
        }
        
        
        int left=0,right=0;
        int start = 0, len = Integer.MAX_VALUE;
        int valid = 0;
        while(right < s.length()){
            char c = s.charAt(right);
            right ++;
            if (need.containsKey(c)){
                map.put(c,map.getOrDefault(c,0)+1);
                if (map.get(c) == need.get(c)){
                    //当value超过127时,Integer将会以对象的形式存储,这两个int值相等但对象不等
                    // => if(map.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            while(valid == need.size()){
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)){
                    if (map.get(d) == need.get(d)){
                        // => if(map.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    map.put(d,map.get(d)-1);
                }
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start,len);
        // => return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
1

谢谢大佬指点,我自己改了一下最后一个用例过不去,看了你的才知道细节决定成败