Leetcode面试经典150题-76.最小覆盖子串

解法都在代码里，不懂就留言或者私信
理论上提交这个就是最优解

1. class Solution {
2.     public String minWindow(String s, String t) {
3.         if(s.length() < t.length()) {
4.             return "";
5.         }
6.         /**转成字符数组 */
7.         char[] sArr = s.toCharArray();
8.         char[] tArr = t.toCharArray();
9.         /**其他情况我们构建一个一个欠账表，这里可以用hashMap，也可以使用数组
10.         hashMap可能更直观一些，我们还有一个遍历count用来记录我们一共欠了多少*/
11.         Map<Character, Integer> countMap = new HashMap<>();
12.         int count = tArr.length;
13.         for(int i = 0; i < tArr.length ; i++) {
14.             countMap.put(tArr[i], countMap.getOrDefault(tArr[i], 0) + 1);
15.         }
16.         /**本题我们使用滑动窗口解题，left是左边界(包含)，right是右边界(不包含)
17.         窗口就是[left, right)，开始值都是0，代表还没有任何数据*/
18.         int left = 0, right = 0;
19.         /**遍历字符串s，进行还款 */
20.         int minWidth = Integer.MAX_VALUE;
21.         /**记录得到最小值时的开始和结束的下标 */
22.         int minStartIndex = 0;
23.         int minEndIndex = 0;
24.         while(right < sArr.length) {
25.             /**只要还是还完的状态就不断的缩小窗口，直到欠债，我们现在就尝试让窗口缩小（left右移），但是我们缩小之前需要记录一下当前的窗口大小 */
26.             while(count == 0) {
27.                 minWidth = Math.min(minWidth, right - left);
28.                 /**如果当前窗口长度就是整个的最小长度，那更新得到最小值时的开始和结束的下标为当前窗口的开始和结束 */
29.                 if(minWidth == right - left) {
30.                     minStartIndex = left;
31.                     minEndIndex = right;
32.                 }
33.                 /**如果left位置这个字符是tArr里右的并且我们当前没有多还，那left退出之后我们实际欠的就多了一个
34.                 如果这个字符不是tArr里真实存在的那就不管*/
35.                 if(countMap.containsKey(sArr[left])) {
36.                     /**有效字符并且之前没有多还，count就增多了1个 */
37.                     if(countMap.get(sArr[left]) >= 0) {
38.                         count ++;
39.                     }
40.                     countMap.put(sArr[left], countMap.get(sArr[left]) + 1);
41.                 }
42.                 left ++;
43.             }
44.             /**走到这肯定是欠债状态，那就尝试right右扩增大窗口试试能不能还上*/
45.             if(countMap.containsKey(sArr[right])) {
46.                 /**如果原来确实欠了这个位置的字符才会影响count */
47.                 if(countMap.get(sArr[right]) > 0) {
48.                     count --;
49.                 }
50.                 countMap.put(sArr[right], countMap.get(sArr[right]) - 1);
51.             }
52.             right ++;
53.         }
54.         /**走出循环如果还是不欠债，试试能不能让窗口在不再次负债的情况下缩小*/
55.         while(count == 0) {
56.             minWidth = Math.min(minWidth, right - left);
57.             if(minWidth == right - left) {
58.                 minStartIndex = left;
59.                 minEndIndex = right;
60.             }
61.             /**如果left位置这个字符是tArr里右的并且我们当前没有多还，那left退出之后我们实际欠的就多了一个
62.             如果这个字符不是tArr里真实存在的那就不管*/
63.             if(countMap.containsKey(sArr[left])) {
64.                 /**有效字符并且之前没有多还，count就增多了1个 */
65.                 if(countMap.get(sArr[left]) >= 0) {
66.                     count ++;
67.                 }
68.                 countMap.put(sArr[left], countMap.get(sArr[left]) + 1);
69.             }
70.             left ++;
71.         }
72.         /**如果最后有答案的话返回得到最小值时的窗口*/
73.         return minWidth == Integer.MAX_VALUE? "" : s.substring(minStartIndex, minEndIndex);
74.     }
75. }

复制代码

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。