字符串：字符串中的最短子字符串(滑动窗口）

本文主要是介绍字符串：字符串中的最短子字符串(滑动窗口），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

题目
哈希表+双指针解法
代码
总结

题目

已知两个字符串s和t，字符串s中可能包含字符串t的所有字符，求s中包含字符串t所有字符的最短的子字符串。
输入：s = “ADDBANCAD”; t = “ABC”;
输出：“BANC”;

哈希表+双指针解法

我们来一起分析此题，求最短的子字符串。

遇到求子字符串，我们会联想到用双指针来扫描子字符串。
遇到求字符串s是否包含字符串t的所有字符。我们可以联想到哈希表来统计字符串中字符出现的次数。
故这道题主要分两个步骤来解决
第一步：定义双指针，向右扫描，求得字符串s包含t的所有字符的子字符串。
第二步：缩短双指针区间，求最短的那个子字符串。
理清题意后，我们可以写出如下代码：

代码

private String minWindow(String s, String t) {
//1.  初始化Map<Character, Integer> charToCounts = new HashMap<>(); //定义哈希表，统计字母出现次数。for(char  ch : t.toCharArray()) {charToCounts.put(ch, charToCounts.getOrDefault(ch, 0) + 1); 统计t中所有字母出现的次数。}int count = charToCounts.size(); // 代表t中字符出现的个数。如“ABC” ， count = 3；// 2. 扫描子字符串int minLength  = Integer.MAX_VALUE;int minStart = 0;int minEnd = 0;while(end < s.length() || (count == 0 && end == s.length())) {if(count > 0) { //char endCh = s.charAt(end);if(s.containsKey(endCh)) {charToCounts.put(endCh, charToCounts.get(endCh) - 1);if(charToCounts.get(endCh) == 0) {count --;}}end++;} else {   
// 3. 扫描最短子字符串if(minLength > (end - start)) {minStart = start;minEnd = end;minLength = minEnd - minStart;}char startCh = s.charAt(start);if(charToCounts.containsKey(startCh)) {charToCounts.put(startCh, charToCounts.get(startCh) + 1);if(charToCounts.get(startCh) == 1) {count++;}}start++;}return minLength < Integer.MAX_VALUE ? s.substring(minStart - minEnd) : "";
}