76 为什么我的滑 动窗口 最后一个 case就是通不过

1. public String minimumWindow(String s, String t) {
   
2.         int l = 0, r = 0, N = s.length() , start = 0, minLen = Integer.MAX_VALUE;
   
3.         Map<Character, Integer> needs = new HashMap();
   
4.         for (char c : t.toCharArray()) {
   
5.             needs.put(c, needs.getOrDefault(c, 0) + 1);
   
6.         }
   
7.         Map<Character, Integer> windows = new HashMap();
   
8.         int match = 0;
   
9.         while (r < N) {
   
10.             char c1 = s.charAt(r);
    
11.             if (needs.containsKey(c1)) {
    
12.                 windows.put(c1, windows.getOrDefault(c1, 0) + 1);
    
13.                 if (windows.get(c1) == needs.get(c1)) {
    
14.                     match++;
    
15.                 }
    
16.             }
    
17.             r++;
    
18. 
    
19.             // find 可行解, pursue 最优解
    
20.             while (match == needs.size()) {
    
21.                 // update
    
22.                 if (r - l < minLen) {
    
23.                     start = l;
    
24.                     minLen = r - l;
    
25.                 }
    
26.                 char c2 = s.charAt(l);
    
27.                 if (needs.containsKey(c2)) {
    
28.                     windows.put(c2, windows.get(c2) - 1);
    
29.                     if (windows.get(c2) < needs.get(c2)) {
    
30.                         match--;
    
31.                     }
    
32.                 }
    
33.                 l++;
    
34.             }
    
35.         }
    
36.         return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    
37.     }

复制代码

跪求各位大佬看下  ,看不出破绽  ,是滑动窗口双指针啊
主要是 最后一个case 输入数据太大了


第二种写法 就能AC通过

1. public String minimumWindow02(String s, String t) {
   
2.         if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) return "";
   
3.         int[] bank = new int[26];
   
4.         int l = 0, r = 0, count = 0;
   
5.         int minLen = Integer.MAX_VALUE;
   
6.         String ans = "";
   
7.         for (int i = 0; i < t.length(); i++) {
   
8.             bank[t.charAt(i) - 'A']++;
   
9.         }
   
10.         while (r < s.length()) {
    
11.             if (bank[s.charAt(r++) - 'A'] > 0) {
    
12.                 bank[s.charAt(r++) - 'A']--;
    
13.                 count++;
    
14.             }
    
15.             //可行解
    
16.             while (count == t.length()) {
    
17.                 if (minLen > r - l) {
    
18.                     minLen = r - l;
    
19.                     ans = s.substring(l, r);
    
20.                 }
    
21.                 // 这里需要解释下
    
22.                 // narrow l
    
23.                 if (bank[s.charAt(l) - 'A'] == 0) {
    
24.                     bank[s.charAt(l) - 'A']++;
    
25.                     count--;
    
26.                 }
    
27.                 l++;
    
28.             }
    
29.         }
    
30.         return ans;
    
31.     }

复制代码

看了很久， 也测了很久。

加一个强转

或者用。equals



大概率是因为你用两个Integer去比较了， 所以会出现错误。

Integer直接比较的话-128到127之间有cache， 范围外就相当于比较地址了。

https://stackoverflow.com/questi ... rent-results-for-12

https://stackoverflow.com/questi ... he-range-128-to-127

发现 解1的match和解2 count 各代表的意思 并不相同, 但是 依旧没有理解  为什么 不行

第一种写法最后是wrong answer还是TLE？

1. public String minimumWindow01(String s, String t) {
   
2.         int count = 0, l = 0, r = 0, minLen = Integer.MAX_VALUE;
   
3.         String ans = "";
   
4.         int[] bank = new int[127];
   
5.         for (char c : t.toCharArray()) {
   
6.             bank[c - 'A']++;
   
7.         }
   
8. 
   
9.         while (r < s.length()) {
   
10.             char c1 = s.charAt(r);
    
11.             if (bank[c1 - 'A'] > 0) { // 匹配了
    
12.                 count++;
    
13.             }
    
14.             bank[c1 - 'A']--;
    
15.             r++;
    
16.             while (count == t.length()) {
    
17.                 if (minLen > r - l) {
    
18.                     minLen = r - l;
    
19.                     ans = s.substring(l, r);
    
20.                 }
    
21.                 char c2 = s.charAt(l);
    
22.                 if (bank[c2 - 'A'] == 0) {// 匹配了
    
23.                     count--;
    
24.                 }
    
25.                 bank[c2 - 'A']++;
    
26.                 l++;
    
27.             }
    
28.         }
    
29.         return ans;
    
30.     }

复制代码

醉了 主贴 第二种方案 有点错误  不能通过  
现在附上能通过  不好意思啊

337845818 发表于 2019-12-23 07:50
看了很久， 也测了很久。

加一个强转

恨不得给你多加点 谢谢大佬

337845818 发表于 2019-12-23 07:50
看了很久， 也测了很久。

加一个强转

谢谢大佬 确实是 Integer cache和 ==惹的祸