leetcode.76 最小覆盖子串Java

亦凉 2024-04-17 21:18 29阅读 0赞

题目描述：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

--------------------

## 思路一 ##

两个指针left和right都指向第一个元素  
然后right指针向右移动，知道找到第一个包含的（包含的可以用一个map统计）  
然后左指针向左移动，看能不能缩小范围，当左指针移动到窗口的字母比T的字母个数还少的时候，再移动右指针。

建立Map字典：

Map<Character, Integer> dicT = new HashMap<>();
    
            for (int i = 0; i < t.length(); i++) { 
                int count = dicT.getOrDefault(t.charAt(i), 0);
                dicT.put(t.charAt(i), count + 1);
            }

用一个数组保存结果：

// 长度 l r
            int[] ans = { -1, 0, 0};

**需要特别注意的是：Map的value是Integer对象，如果使用==比较对象的话，是比较的地址，这个时候要么用equals方法，或者用.intValue**

if (dicT.containsKey(c) && Objects.equals(windowCounts.get(c), dicT.get(c))) { 
                    formed++;
                }

或者

if (dicT.containsKey(c) && windowCounts.get(c).intValue() == dicT.get(c).intValue()) { 
                    formed++;
                }

如果直接对象相等是错的。

完整代码：

package Solution;
    
    import java.util.HashMap;
    import java.util.Map;
    
    /** * @Author : fanc:最小覆盖子串 * @Date : 2019-08-26 20:16 */
    public class Solution76 { 
        public static String minWindow(String s, String t) { 
    
            if (s.length() == 0 || t.length() == 0) { 
                return "";
            }
    
            Map<Character, Integer> dicT = new HashMap<>();
    
            for (int i = 0; i < t.length(); i++) { 
                int count = dicT.getOrDefault(t.charAt(i), 0);
                dicT.put(t.charAt(i), count + 1);
            }
    
            //需要的数目
            int required = dicT.size();
    
            //已经构建的数目
            int formed = 0;
    
            // 左右两个指针
            int l = 0, r = 0;
    
            // 窗口字母个数
            Map<Character, Integer> windowCounts = new HashMap<>();
    
            // 长度 l r
            int[] ans = { -1, 0, 0};
    
            while (r < s.length()) { 
                char c = s.charAt(r);
                int count = windowCounts.getOrDefault(c, 0);
                windowCounts.put(c, count + 1);
    
                if (dicT.containsKey(c) && windowCounts.get(c).intValue() == dicT.get(c).intValue()) { 
                    System.out.println(1);
                    formed++;
                }
    
                while (l <= r && formed == required) { 
                    System.out.println("l" + l + "r" + r);
                    c = s.charAt(l);
                    if (ans[0] == -1 || r - l + 1 < ans[0]) { 
                        ans[0] = r - l + 1;
                        ans[1] = l;
                        ans[2] = r;
    
                    }
    
                    //尝试左指针向右移动
                    l ++;
                    windowCounts.put(c, windowCounts.get(c) - 1);
                    if (dicT.containsKey(c) && windowCounts.get(c).intValue() < dicT.get(c).intValue()) { 
                        formed --;
                    }
                }
                r ++;
            }
    
            return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    
        }
    }

--------------------

## 优化方法：优化的滑动窗口 ##

我们只需要考虑S包含T的元素，因此可以把S包含T的元素单独列出来做一个filter，然后遍历这个filter。

/** * @Author : fanc * @Date : 2019-09-01 13:56 */
    public class Solution76_2 { 
        public String minWindow(String s, String t) { 
            if (t.length() == 0 || s.length() == 0) { 
                return "";
            }
    
            Map<Character, Integer> dicT = new HashMap<>();
    
            for (int i = 0; i < t.length(); i++) { 
                int count = dicT.getOrDefault(t.charAt(i), 0);
                dicT.put(t.charAt(i), count + 1);
            }
    
            List<Pair<Integer, Character>> filterS = new ArrayList<>();
    
            for (int i = 0; i < s.length(); i++) { 
                char c = s.charAt(i);
                if (dicT.containsKey(c)) { 
                    filterS.add(new Pair<>(i, c));
                }
            }
    
            int l = 0, r = 0, formed = 0;
            int required = dicT.size();
            int[] ans = { -1, 0, 0};
    
            Map<Character, Integer> window = new HashMap<>();
    
            while (r < filterS.size()) { 
                char c = filterS.get(r).getValue();
                int count = window.getOrDefault(c, 0);
                window.put(c, count + 1);
                if (window.get(c).intValue() == dicT.get(c).intValue()) { 
                    formed++;
                }
                while (l <= r && formed == required) { 
                    c = filterS.get(l).getValue();
                    int start = filterS.get(l).getKey();
                    int end = filterS.get(r).getKey();
                    if (ans[0] == -1 || end - start + 1 < ans[0]) { 
                        ans[0] = end - start + 1;
                        ans[1] = start;
                        ans[2] = end;
                    }
    
                    l++;
                    window.put(c, window.get(c) - 1);
                    if (window.get(c).intValue() < dicT.get(c).intValue()) { 
                        formed--;
                    }
                }
                r ++;
            }
            return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    
        }
    }

**在Java里面使用Pair来构建一个存放key和value的list**  
可以使用getKey和getValue的方法来获取Pair里面的key和value  
Array初始长度为0，之后每次按照之前的1.5倍来扩容，在这个例子上面效率比LinkedList高

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/a4d28e9f0b6c4eb8b2988eade0ee43e5.png